two-Sum及其引申相关

[twoSum]https://leetcode.com/problems/two-sum/description/

1.暴力解法
两摞扑克牌，分别遍历，从第一摞牌中拿出一个，然后从第二摞牌中依次拿出扑克牌进行求和，等于target就满足条件return

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result =  new int[2];
        if (nums.length < 2) {
            return result;
        }
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i+1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    result[0] = i;
                    result[1] = j;
                    return result;
                }
            } 
        }
        return result;
    }
}

2.暴力解法的时间复杂度为O(n^2)，优化一下，由于题目要求输出索引，想到hashmap

//循环从0到n-1，遍历到第i个元素的时候，前i个都插入到了hashmap
//先看看在hash里nums[i]是否存在，如果存在，就把索引压进去
//如果等于空就再把剩下的target-i放进hash里，重复同样的步骤

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            if (map.get(nums[i]) != null) {
                int[] result = {map.get(nums[i]) , i};
                return result;
            }
            map.put(target - nums[i], i);
        }
        
        int[] result = {};
        return result;
    }
}

3.不要求输出索引，而是要求输出数组的twoSum，前后指针

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] result = new int[2];
        Arrays.sort(numbers);
        int first = 0, second = numbers.length-1;
        while (first < second) {
            if (numbers[first] + numbers[second] == target) {
                result[0] = numbers[first];
                result[1] = numbers[second];
                return result;
            }
            if (numbers[first] + numbers[second] > target) {
                second--;
            }
            if (numbers[first] + numbers[second] < target) {
                first++;
            }
        }
        return result;
    }
}

3Sum
[3Sum] https://leetcode.com/problems/3sum/description/
这道题的思路也是双指针，注意使用双指针的时候一定要对数组排序。本题给的List，就要使用ArrayList把原数组的结果存入，同时在调用2Sum函数时候要注意再使用ArrayList存输出的数组，最后并入之前的结果中。

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);
        
        for (int i = 0; i < nums.length - 2; i++) {
            //去重
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int first = i + 1, second = nums.length-1;
            int target = -nums[i];
            twoSum(nums,first,second,target,result);
        }
        return result;
    } 
    public void twoSum(int[] nums, int first, int second, int target, List<List<Integer>> result) {
        while (first < second) {
            if (nums[first] + nums[second] == target) {
                ArrayList<Integer> triple = new ArrayList<>();
                triple.add(-target);//因为定义的就是target，所以此处不能用nums[i]，传不进来
                triple.add(nums[first]);
                triple.add(nums[second]);
                result.add(triple);
                first++;
                second--;
                //去重
                while (first < second && nums[first] == nums[first - 1]) {
                    first++;
                }
                while (first < second && nums[second] == nums[second + 1]) {
                    second--;
                }
            } else if (nums[first] + nums[second] < target) {
                first++;
            } else {
                second--;
            }
        }
    }
}