LeetCode从两数之和到K数之和

LeetCode上第一题关于两数之和的问题，从而扩展到3数之和，4数之和等，其中关于解决重复集合的问题是关键以及多层遍历是解题的关键，以下归纳并总结其中在解题的过程中遇到的问题。

1.两数之和

https://leetcode.com/problems/two-sum/
这是leetcode的第一道题，也是入门简单等级。其中不包含重复数字也只有一组唯一解，相对来说只要从一个下标的数字开始并从当前的下一个开始到结束找到有符合的即为结果。
注意：这里的数字范围包含负数，目标值也可能为负数，因此不能采用传统双指针的方式去解决。

最简单的方式即采用map存储出现过的数字及对应下标，map的get为O(1)。

class Solution {
   
    public int[] twoSum(int[] nums, int target) {
   
     Map<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<nums.length;i++){
   
            int toFindVal=target-nums[i];
            if (map.containsKey(toFindVal)){
   
                return new int[]{
   i,map.get(toFindVal)};
            }
            map.put(nums[i],i);
        }
       
        return new int[]{
   };
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

而适用于双指针的场景，左指针往后一定是结果变大，右指针往前一定是结果变小。

15.三数之和

https://leetcode.com/problems/3sum/
从两个数字扩展到三个数字，并且不包含重复方案，且元素下标也不相等，但目标和为0。依然可以利用两数之和的方式对每个元素找与之对应的相反数是否存在，并跳过连续相等的元素。
同时对于多于两个数的情况，需要先对数组进行排序，这样才可以保证从左往右或从右往左根据数据大小进行范围的缩小。
注意：约束中，数值的范围代表用和的方式不会存在int的溢出，因此不需要考虑用long

• -10^5 <= nums[i] <= 10^5

class Solution {
   
    public List<List<Integer>> threeSum(int[] nums) {
   
      List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length < 3) {
   
            return result;
        }
        Arrays.sort(nums);
        if(nums[0]>0){
   
            return result;
        }
        for (int i = 0; i < nums.length - 2;i++) {
   
            twoSum(nums,i,result);
            while (i+1<nums.length&& nums[i]==nums[i+1]){
   
                i++;
            }
        }
        return  result;
    }

    public static void twoSum(
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25