n数之和

n数之和是一类题，解题思路是首先固定前n-2个数，然后使用双指针遍历最后的两个数，减少一次循环，降低时间复杂度，从而达到不超时的目的

两数之和

输入一个递增排序的数组和一个数字target，在数组中查找两个数，使得它们的和正好是target。如果有多对数字的和等于target，则输出任意一对即可。

三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

四数之和

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

解法剖析

两数之和（固定0个数，双指针遍历最后两个数）

求两数之和时,如果只有一个,直接对数组进行排序，然后使用双指针，依次遍历

Arrays.sort(nums);
int l = 0, r = nums.length - 1;
while (l < r) {
    if (target - nums[l] < nums[r]) r--;
    else if (target - nums[l] > nums[r]) l++;
    else {
      //得到一个解,nums[l],nums[r]
      l++;
      r--;
    }
}

三数之和（固定第一个数，双指针遍历最后两个数）

求三数之和时，只需遍历（固定）第一个数，然后对另外的两个数使用双指针，依次遍历，双指针的遍历过程如两数之和的解

四数之和

求四数之和时，只需遍历（固定）前两个数,然后对另外的两个数使用双指针，依次遍历，双指针的遍历过程如下：

for (int i = 0; i < nums.length; i++) {
    for (int j = i + 1; j < nums.length; j++) {
        l = j + 1;
        r = nums.length - 1;
        while (l < r) {
            int sum = nums[i] + nums[j] + nums[l] + nums[r];
            if (sum == target) {
                //得到一组解：nums[i], nums[j], nums[l], nums[r]
                l++;
                r--;
            } else if (sum < target) {
                l++;
            } else {
                r--;
            }
        }
    }
}

赏

谢谢你请我吃糖果

微信