leetcode-n-sum总结

总结一下leetcode中遇见的2-sum, 3-sum, 4-sum问题，并扩展到n-sum。

1. 两数之和 - 力扣（LeetCode）

梦开始的地方，不多说。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            int num = nums[i];
            if(map.containsKey(target - num)){
                return new int[]{i, map.get(target - num)};
            }
            else map.put(num, i);
        }
        return null;
    }
}

15. 三数之和 - 力扣（LeetCode）

写完两数之和可能觉得三数之和也可以用哈希法，但是貌似哈希法非常麻烦。本题较为简单的思路为三指针法（扩展版的双指针），时间复杂度为O(n^2)。

步骤如下：

1. 首先对数组进行排序，之后可以立刻对算法进行剪枝操作，条件为 if(nums[0] > 0) return res;

2. 给定一个指针i，外层遍历数组元素；

3. 给定两个指针left、right，left = i + 1, right = nums.length - 1，如果nums[i] + nums[left] + nums[right] == 0，则将结果加入到列表中，同时更新left和right（注意去重，防止加入相同的结果），如果 nums[i] + nums[left] + nums[right] > 0，则right--，否则left++；

 4. 返回结果。

 图示如下：

class Solution {
    //三指针法（双指针的扩展），时间负责度O(n^2)
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        //先给数组排序
        Arrays.sort(nums);
        //第一层循环
        for(int i = 0; i < nums.length - 2; i++){
            //剪枝
            if(nums[i] > 0) return res;
            //去重
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            int target = 0 - nums[i];
            //二层循环
            int left = i + 1,right = nums.length - 1;
            while(left < right){
                //内层列表要放在这里
                List<Integer> ls = new ArrayList<>();
                int leftVal = nums[left], rightVal = nums[right];
                int sum = leftVal + rightVal;
                if(sum == target){
                    ls.add(nums[left]);
                    ls.add(nums[right]);
                    ls.add(nums[i]);
                    res.add(ls);
                    //left和right要去重，防止加入相同的组合
                    while(left < right && nums[left] == leftVal) left++;
                    while(left < right && nums[right] == rightVal) right--;
                }
                else if(sum < target)left++;
                else right--;
            }
        }
        return res;
    }
}

18. 四数之和 - 力扣（LeetCode）

四数之和为三数之和的加强版，采用四指针法（双指针法的加强版），时间复杂度为O(n^3)。

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        //排序
        Arrays.sort(nums);
        for(int i = 0; i < nums.length - 3; i++){
            //一级剪枝
            if(nums[i] > target && nums[i] >= 0) return res;
            //去重
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            for(int j = i + 1; j< nums.length - 2; j++){
                //二级剪枝
                if(nums[i] + nums[j] > target && nums[i] + nums[j] >= 0) break;
                //去重
                if(j > i + 1 && nums[j] == nums[j - 1]) continue;
                int left = j + 1, right = nums.length - 1;
                while(left < right){
                    List<Integer> ls = new ArrayList<>();
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if(sum == target){
                        ls.add(nums[i]);
                        ls.add(nums[j]);
                        ls.add(nums[left]);
                        ls.add(nums[right]);
                        //left去重
                        while(left < right && nums[left] == nums[left + 1]) left++;
                        while(left < right && nums[right] == nums[right - 1]) right--;
                        left++;
                        right--;
                        res.add(ls);
                    }
                    else if(sum < target) left++;
                    else    right--;
                }
            }
        }
        return res;
    }
}

【剪枝条件】

注意到当target为负数的时候，无法通过nums[i]> target来给程序做剪枝操作。举个例子[-5,-4,1,2], target = -9中，不能因为-5比-9大就直接做剪枝操作。这里的剪枝条件是nums[i] > target && nums[i] >= 0或者nums[i] + nums[j] > target && nums[i] + nums[j]  >= 0：

当nums[i] + nums[j] >= 0的时候，由于数组是非递减的，所以nums[i]和nums[j]中至少有一个非负数，nums[j]之后的也一定为非负数，又因为nums[i] + nums[j] > target，所以nums[i]、nums[j]与之后的数字相加的结果也必定大于target，可以直接剪枝。

【n-sum】

我们可以通过三数之和和四数之和把问题推广到n-sum上，大概的思路一致。通过多指针法可以把算法的复杂度从O(k ^ n)降低到O(k ^ (n - 1))。都是外层循环➕内层双指针的套路，剪枝操作的条件也大概相似。