LeetCode Exercise - Two Questions About Finding Sum of Array Elements

1. 数组中和为 0 的三个数

1.1 题目描述

剑指 Offer II 006. 排序数组中两个数字之和

给定一个已按照 升序排列  的整数数组 numbers ,请你从数组中找出两个数满足相加之和等于目标数 target .

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值.numbers 的下标 从 0 开始计数 ,所以答案数组应当满足 0 <= answer[0] < answer[1] < numbers.length .

假设数组中存在且只存在一对符合条件的数字,同时一个数字不能使用两次.

示例 1：

输入：numbers = [1,2,4,6,10], target = 8
输出：[1,3]
解释：2 与 6 之和等于目标数 8 .因此 index1 = 1, index2 = 3 .

示例 2：

输入：numbers = [2,3,4], target = 6
输出：[0,2]

示例 3：

输入：numbers = [-1,0], target = -1
输出：[0,1]

1.2 解题思路与代码

1.2.1 解题思路

This question is to find if there are two numbers in an array that are equal to a given number,It can be considered that there is a brute force solution to traverse the array in two layers and sum it up in turn,But the same time complexity is O(n^2) 太高了.The title has stipulated that the array is an array sorted in ascending order,We can use the double pointer to move from both sides to the middle to calculate the sum of the numbers pointed to by the two pointers,再与 target Make a comparison move.First let the left pointer l Pointer 0 位置,右指针 r 指向数组最后一位,Then calculate the sum of the numbers pointed to by the two pointers,At this time, the calculated sum will appear in the following three cases：

• 如果和等于 target 退出循环并返回 l 和 r（Because the question stipulates that there is only one answer）
• 如果和小于 target,Because the array is sorted from small to large,At this point, move the left pointer to the right to make the sum of the two numbers larger
• Similarly if and greater than target,Now move the right pointer to the left,This makes the sum of the two numbers smaller

以题目示例 numbers = [1,2,4,6,10], target = 8 为例进行图解：
首先让 l 和 r 指向首位,此时 l 和 r The sum of the pointing numbers is 11,大于 target ,因此让 r 左移

r 左移之后,此时 l=0,r=3,两数之和为 7 ,小于 target 于是让 l 右移

l 右移之后,此时 l=1,r=3,两数之和为 8 ,等于 target 满足题意返回 [1, 3]

1.2.2 代码

class Solution {
    
    public int[] twoSum(int[] numbers, int target) {
    
        int l = 0;
        int r = numbers.length - 1;
        int[] ans = new int[2];
        while (l < r) {
    
            if (numbers[l] + numbers[r] == target) {
    
                ans[0] = l;
                ans[1] = r;
                break;
            } else if (numbers[l] + numbers[r] < target) {
    
                l++;
            } else {
    
                r--;
            }
        }
        return ans;
    }
}

1.2.3 测试结果

通过测试

2. 数组中和为 0 的三个数

2.1 题目描述

剑指 Offer II 007. 数组中和为 0 的三个数
给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a ,b ,c ,使得 a + b + c = 0 ？请找出所有和为 0 且 不重复 的三元组.

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：

输入：nums = []
输出：[]

示例 3：

输入：nums = [0]
输出：[]

2.2 解题思路与代码

2.2.1 解题思路

This question is actually the same as the one above,Just from the sum of the two numbers target The sum of three numbers becomes zero.我们可以转换一下思想,If we grab a number in an array num,Then it is programmed to find the sum of the two numbers in the remaining numbers -num.我们在进一步,对数组 nums 进行排序,Then we traverse the array from left to right：

• 遍历第一位 nums[0] 时,我们就需要在 [1, n-1] Find the sum of two numbers equal to -num[0]
• Traverse to the second position nums[1] 时,我们就需要在 [2, n-1] Find the sum of two numbers equal to -num[1]
• Traverse to the third position nums[2] 时,我们就需要在 [3, n-1] Find the sum of two numbers equal to -num[2]
  ……
• 依次类推

Since we have already sorted the array,Then the numbers in the following search range are sorted in ascending order,Here you can see that it is exactly the same as the above question,只不过 target 变成了 -nums[i],查找范围变成 [i+1, n-1].从上面的分析,We can loop through the array in the outer layer,A double pointer slave is used inside the loop [i+1, n-1] Find the sum of two numbers equal to -num[i] 的两个数.Same topic as above,也有三种情况：

• When the sum of the two numbers is less than -num[i] 时,l 右移
• 当两数之和大于 -num[i] 时,l 左移
• 当两数之和等于 -num[i] 时,i、l、r The numbers in the three positions are put into the result list,然后 l 右移、r 左移.

这里需要注意,The title requires that no repeated numbers appear,因此当 nums[i] 等于 nums[i-1] 时,跳过本次循环,同理 nums[l] 等于 nums[l-1]、 nums[r] 等于 nums[r+1] also needs to be skipped.下面是数组 [-1,0,1,2,-1,-4] 查找的过程,首先 i=0,我们使用 l 和 r 在 [1, 5] Find the sum of two numbers equal to 4 的两个数,当 l 等于 r When the inner loop is launched.然后 i=1 此时在 [2, 5] Find the sum of two numbers equal to 1 此时 l=2 和 r=5 The sum of the two numbers referred to is equal to 1 满足条件,放入结果数组中.Then repeat the above process,直到数组遍历完成.

2.2.2 代码

class Solution {
    
    public List<List<Integer>> threeSum(int[] nums) {
    
        List<List<Integer>> ans = new ArrayList<>();
        if (nums.length == 0) {
    
            return ans;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
    
            if (i > 0 && nums[i] == nums[i - 1]) {
    
                continue;
            }
            int target = -nums[i];
            int l = i + 1;
            int r = nums.length - 1;
            while (l < r) {
    
                if (nums[l] + nums[r] == target) {
    
                    ans.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    do {
    
                        l++;
                    } while (l < r && nums[l] == nums[l - 1]);
                    do {
    
                        r--;
                    } while (l < r && nums[r] == nums[r + 1]);

                } else if (nums[l] + nums[r] < target) {
    
                    l++;
                } else {
    
                    r--;
                }
            }

        }
        return ans;
    }
}

2.2.3 测试结果

通过测试

3.总结

• The first question is handled using double pointers,The sum of the two numbers is less than the target,左指针右移;大于目标,右指针左移;等于目标,Exit the loop to return the result
• The second question is a variant of the first question,排序后遍历数组,The same is to find the sum of two numbers equal to a certain number in the following array
• The second question needs to be de-duplicated,Hence three pointers i、l、r If after the move is equal to the number before the move,Then need to keep moving