解密N数之和问题的秘密

傷城~ 2024-02-18 10:37 30阅读 0赞

#### 目录 ####

*   *  两数之和
     *  三数之和

![在这里插入图片描述][2ccb782122d04732a5d9262fd392c53f.png]

### 两数之和 ###

我们来看力扣第一题  
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。  
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。  
你可以按任意顺序返回答案。

> 示例 1：  
> 输入：nums = \[2,7,11,15\], target = 9  
> 输出：\[0,1\]  
> 解释：因为 nums\[0\] + nums\[1\] == 9 ，返回 \[0, 1\] 。  
> 示例 2：  
> 输入：nums = \[3,2,4\], target = 6  
> 输出：\[1,2\]  
> 示例 3：  
> 输入：nums = \[3,3\], target = 6  
> 输出：\[0,1\]

这个题我们看到之后想到最简单的思路就是两个for循环，里层数加外层数之和等于目标数，我们就返回两个下标。

public int[] twoSum(int[] nums, int target) {
        
            // 遍历数组
            for (int i = 0; i < nums.length; i++) {
        
                // 内层循环从i+1开始，因为i已经试过
                for (int j = i+1; j < nums.length; j++) {
        
                    // 如果两个数相加等于target，则返回下标
                    if(nums[i] + nums[j] == target){
        
                        return new int[]{
        i,j};
                    }
                }
            }
            // 如果没有找到，则返回空数组
            return new int[0];
        }

但是这个解法的时间复杂度很高，我们还有更好的方法就是使用哈希表，这种方式我们可以把寻找target-x的时间复杂度由O（N）变为O（1）。  
对于每一个x，我们可以先在哈希表中查找是否存在target-x，如果不存在即可把x放入哈中，这样可以避免与自己相遇。  
代码实现如下：

public int[] twoSum1(int[] nums, int target) {
        
            // 创建一个HashMap
            HashMap<Integer,Integer> map =  new HashMap<>();
            // 遍历数组
            for (int i = 0; i < nums.length; i++) {
        
                // 如果HashMap中包含target-nums[i]，则返回该值和i
                if(map.containsKey(target - nums[i])){
        
                    return new int[]{
         map.get(target-nums[i]),i};
                }
                // 将nums[i]作为key，i作为value，放入HashMap中
                map.put(nums[i],i);
            }
            // 如果没有找到，则返回一个空数组
            return new int[0];
        }

### 三数之和 ###

我们来看力扣15题的描述  
给你一个整数数组 nums ，判断是否存在三元组 \[nums\[i\], nums\[j\], nums\[k\]\] 满足 i != j、i != k 且 j != k ，同时还满足 nums\[i\] + nums\[j\] + nums\[k\] == 0 。请  
你返回所有和为 0 且不重复的三元组。  
注意：答案中不可以包含重复的三元组。

> 示例 1：  
> 输入：nums = \[-1,0,1,2,-1,-4\]  
> 输出：\[\[-1,-1,2\],\[-1,0,1\]\]  
> 解释：  
> nums\[0\] + nums\[1\] + nums\[2\] = (-1) + 0 + 1 = 0 。  
> nums\[1\] + nums\[2\] + nums\[4\] = 0 + 1 + (-1) = 0 。  
> nums\[0\] + nums\[3\] + nums\[4\] = (-1) + 2 + (-1) = 0 。  
> 不同的三元组是 \[-1,0,1\] 和 \[-1,-1,2\] 。  
> 注意，输出的顺序和三元组的顺序并不重要。  
> 示例 2：  
> 输入：nums = \[0,1,1\]  
> 输出：\[\]  
> 解释：唯一可能的三元组和不为 0 。  
> 示例 3：  
> 输入：nums = \[0,0,0\]  
> 输出：\[\[0,0,0\]\]  
> 解释：唯一可能的三元组和为 0 。

这道题使用三个for循环时间复杂度太高了不可取，我们使用排序加双指针来做这道题。

public List<List<Integer>> threeSum(int[] nums) {
        
            int n = nums.length;
            Arrays.sort(nums);
            List<List<Integer>> ans = new ArrayList<>();
            //枚举a
            for (int first = 0; first < n; first++) {
        
                //和上一次的枚举数不相同
                if (first > 0 && nums[first] == nums[first - 1]) {
        
                    continue;
                }
                int third = n - 1;
                int target = -nums[first];
                //枚举b
                for (int second = first + 1; second < n; second++) {
        
                    if (second > first + 1 && nums[second] == nums[second - 1]) {
        
                        continue;
                    }
                    //保证b的指针在c的指针的左侧
                    while (second < third && nums[second] + nums[third] > target) {
        
                        third--;
                    }
                    if (second == third) {
        
                        break;
                    }
                    if (nums[second] + nums[third] == target) {
        
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[first]);
                        list.add(nums[second]);
                        list.add(nums[third]);
                        ans.add(list);
                    }
                }
    
            }
            return ans;
        }

1.  首先，对输入的数组进行排序。这样可以保证在后续的查找过程中，相邻的元素是有序的，便于排除重复的情况。
2.  初始化一个空的答案列表，用于存储满足条件的三元组。
3.  枚举数组的第一个元素作为第一个指针（a），第二个元素作为第二个指针（b），最后一个元素作为第三个指针（c）。
4.  在枚举a的过程中，如果发现a和上一次枚举的元素相同，则跳过此次循环，继续枚举下一个不同的元素。
5.  在枚举b的过程中，如果发现b和上一次枚举的元素相同，则跳过此次循环，继续枚举下一个不同的元素。
6.  在枚举b的过程中，保证b的指针在c的指针的左侧。
7.  当b指针小于c指针时，判断当前元素之和是否等于目标值。如果等于目标值，则将当前三元组添加到答案列表中。
8.  继续枚举a和b，直到所有可能的组合都被检查完毕。
9.  返回答案列表。

还有更多好玩的题目例如：[四数之和][Link 1]等等。

[2ccb782122d04732a5d9262fd392c53f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/18/e882b9225f474df0a519537e0843b3e1.png
[Link 1]: https://leetcode.cn/problems/4sum/description/