Leetcode: 2 sum , 3 sum , 3 sum closest , 4 sum 题解

- October 13, 2016

最近在Leetcode 上刷了这么几道题目，觉得可以记录一下：

2 sum ：

题意：给定一个int数组nums以及一个int型的target。求这个数组中的两个数字和等于target。输出他们在数组中的下标。因为输出的是他们在原数组中的下标，所以不方便上来对原数组排序。

解法：两层循环的遍历，对第i个下标 i

\in

[0,nums.length-1) , 查找从i+1 开始所有的数组内容nums[j]，是否满足nums[i] + nums[j] == target 复杂度O(

n^{2}

)

public class Solution{
    public int[] twoSum(int[] nums,int target){
        int N = nums.length;
        int[] res = new int[2];
    
        for(int i = 0; i < N-1 ; i++ ){
            for(int j = i + 1; j<N ; j++){
                int sum = nums[i] + nums[j];
                if(sum == target){
                    res[0] = i + 1;
                    res[1] = j + 1;
                    System.out.println("index1="+i+1+", index2="+j+1);
                    return res;
                }
            }
        }

        return res;
    }
}

3 sum ：

题意：和2sum 意思差不多，给定一个int型数组，在其中找到3个int和为0 (即target 是0)，和2sum不同的是这次输出的结果不是下标，而是直接是那几个元素，

解法：因为输出的不是下标，所以我们可以对原数组进行排序Arrays.sort() 复杂度O(nlogn)。因为求得是三个数的和，结合之前的2sum 我们可以先选定一个数字i

\in

[0,nums.length-2)，然后在剩下的i+1到后面所有的元素中挑出两个，假设下标从左到右分别为m,n；如果
nums[i] + nums[n] + nums[m] == target 则添加到结果中，如果小于target那么m应该向右移动；如果大于target那么n应该向左移动。
这里有几个细节要考虑:
1. m和n在移动的时候在确定m小于n的前提下，要判断是否移动后的和原来内容一样。如果是则要跳过，否则结果集里面会有重复。
2. i也要考虑重复问题

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
     List<List<Integer>> result = new ArrayList<List<Integer>>();
        int target = 0;
        int len = nums.length;
        Arrays.sort(nums);
        for(int i = 0 ;i<len-2;i++){
            if(i != 0 && nums[i] == nums[i-1]  ){
                continue;
            }
            int left = i + 1;
            int right = len - 1;
            while(left < right){
                int sum = nums[left] + nums[right] + nums[i];
                if( sum == target) {
                    ArrayList<Integer> tmp = new ArrayList<Integer>();
                    tmp.add(nums[i]);
                    tmp.add(nums[left]);
                    tmp.add(nums[right]);
                    result.add(tmp);
                    left ++;
                    right --;
                    while(nums[left] == nums[left - 1] && left < right){
                        left ++;
                    }
                    while(nums[right] == nums[right + 1] && left < right){
                        right --;
                    }
                }else if(sum < target){
                    left ++;
                }else{
                    right --;
                }
            }
            
        }
            return result;
    }
}

3 sum closest

题意：这题和3sum其实差不多，区别在于，这里找的是和target最接近的值。
解法：这就需要多记录一个当前最接近target的，然后在循环的过程中更新这个值。

public class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int res = Integer.MAX_VALUE / 2;
        Arrays.sort(nums);
        for(int i = 0;i<nums.length;i++){
            if(i != 0 && nums[i] == nums[i-1] ){
                continue;
            }
            int left = i + 1;
            int right = nums.length -1 ;
            while(left < right){
                int sum = nums[i] + nums[left] + nums[right];
                if(sum == target) {
                    return sum;
                }
                else if(sum < target){
                    left ++;
                }else{
                    right --;
                }
                res = Math.abs(sum - target) < Math.abs(res - target) ? sum : res; 
            }
        }
        return res ;
        
    }
}

4 sum

题意：在一个数组里，找4个数的和等于target
解法：可以理解成是3 sum的升级版，区别在于，需要先选一个数A，再选一个数B，然后再在剩余序列中找2个数m和n求和为target，说白了多加一层循环的嵌套而已。

public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        int len = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        for(int i = 0 ;i < len -3;i++){
            if(i != 0 && nums[i - 1] == nums[i]){
                continue;
            }
            for(int j = i + 1 ; j<len -2;j++){
                if(j != i+1  && nums[j-1] == nums[j]){
                    continue;
                }
                int left = j + 1;
                int right = len - 1;
                while(left < right ){
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if( sum == target ){
                        List<Integer> tmp = new ArrayList<Integer>();
                        tmp.add(nums[i]);
                        tmp.add(nums[j]);
                        tmp.add(nums[left]);
                        tmp.add(nums[right]);
                        result.add(tmp);
                        left ++;
                        right--;
                        while(left < right && nums[left] == nums[left -1 ]){
                            left ++;
                        }
                        while(left < right && nums[right] == nums[right + 1]){
                            right --;
                        }
                    }else if(sum < target){
                        left++;
                    }else{
                        right--;
                    }
                }
            }
        }
        return result;
    }
}

附：这里有一个小细节，为什么在循环过后可以不理会前面的，比如3 sum的时候我先排序，然后选定一个数A，然后只要在A之后的序列中找两个数，而不是在A前面的数组和A后面的数组一起找这两个数求和等于target？（假定m n A 都是下标）
证明：假设我们找的数字m在A之前，n在A之后。那么nums[m] + nums[n] == target － nums[A]; 这就等价于我们在之前找到m的时候就能列出这样的等式nums[A] + nums[n] == target － nums[m]
所以每次只要在挑出来的那个数字之后的数组中查找就行了。

Search This Blog

YG Overflow