[Leetcode] 3Sum 4Sum 3Sum Closet 多數(shù)和

trigkit4 發(fā)布于2019-08-14 12:29 / 2741人閱讀

摘要：為了避免得到重復(fù)結(jié)果，我們不僅要跳過重復(fù)元素，而且要保證找的范圍要是在我們最先選定的那個(gè)數(shù)之后的。而計(jì)算則同樣是先選一個(gè)數(shù)，然后再剩下的數(shù)中計(jì)算。

2Sum

在分析多數(shù)和之前，請(qǐng)先看Two Sum的詳解

3Sum

請(qǐng)參閱：https://yanjia.me/zh/2019/01/...

雙指針法 復(fù)雜度

時(shí)間 O(N^2) 空間 O(1)

思路

3Sum其實(shí)可以轉(zhuǎn)化成一個(gè)2Sum的題，我們先從數(shù)組中選一個(gè)數(shù)，并將目標(biāo)數(shù)減去這個(gè)數(shù)，得到一個(gè)新目標(biāo)數(shù)。然后再在剩下的數(shù)中找一對(duì)和是這個(gè)新目標(biāo)數(shù)的數(shù)，其實(shí)就轉(zhuǎn)化為2Sum了。為了避免得到重復(fù)結(jié)果，我們不僅要跳過重復(fù)元素，而且要保證2Sum找的范圍要是在我們最先選定的那個(gè)數(shù)之后的。

代碼

public class Solution {
    public List> threeSum(int[] nums) {
        Arrays.sort(nums);
        ArrayList> res = new ArrayList>();
        for(int i = 0; i < nums.length - 2; i++){
            // 跳過重復(fù)元素
            if(i > 0 && nums[i] == nums[i-1]) continue;
            // 計(jì)算2Sum
            ArrayList> curr = twoSum(nums, i, 0 - nums[i]);
            res.addAll(curr);
        }
        return res;
    }
    
    private ArrayList> twoSum(int[] nums, int i, int target){
        int left = i + 1, right = nums.length - 1;
        ArrayList> res = new ArrayList>();
        while(left < right){
            if(nums[left] + nums[right] == target){
                ArrayList curr = new ArrayList();
                curr.add(nums[i]);
                curr.add(nums[left]);
                curr.add(nums[right]);
                res.add(curr);
                do {
                    left++;
                }while(left < nums.length && nums[left] == nums[left-1]);
                do {
                    right--;
                } while(right >= 0 && nums[right] == nums[right+1]);
            } else if (nums[left] + nums[right] > target){
                right--;
            } else {
                left++;
            }
        }
        return res;
    }
}

2019/01
Go

func threeSum(nums []int) [][]int {
    // sort the slice to avoid duplicate and also use two pointers
    sort.Slice(nums, func(i, j int) bool {
        return nums[i] < nums[j]
    })
    res := [][]int{}
    for i := 0; i < len(nums); i++ {
        // skip duplicate numbers
        if i != 0 && nums[i] == nums[i - 1] {
            continue
        }
        // convert into a twoSum problem
        res = twoSum(nums, i + 1, nums[i], res)
    }
    return res
}

func twoSum(nums []int, start, first int, res [][]int) [][]int {
    left := start
    right := len(nums) - 1
    for left < right {
        sum := nums[left] + nums[right]
        if sum == 0 - first {
            res = append(res, []int{first, nums[left], nums[right]})
            left++
            right--
            // skip duplicate numbers from left side
            for left < len(nums) && left > 0 && nums[left] == nums[left - 1] {
                left++
            }
            // skip duplicate numbers from right side
            for right >= 0 && right < len(nums) - 1 && nums[right] == nums[right + 1] {
                right--
            }
        } else if sum > 0 - first {
            right--
        } else if sum < 0 - first {
            left++
        }
    }
    return res
}

4Sum 雙指針法 復(fù)雜度

時(shí)間 O(N^3) 空間 O(1)

思路

和3Sum的思路一樣，在計(jì)算4Sum時(shí)我們可以先選一個(gè)數(shù)，然后在剩下的數(shù)中計(jì)算3Sum。而計(jì)算3Sum則同樣是先選一個(gè)數(shù)，然后再剩下的數(shù)中計(jì)算2Sum。

代碼

public class Solution {
    public List> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        ArrayList> res = new ArrayList>();
        for(int i = 0; i < nums.length - 3; i++){
            if(i > 0 && nums[i] == nums[i-1]) continue;
            List> curr = threeSum(nums, i, target - nums[i]);
            res.addAll(curr);
        }
        return res;
    }
    
    private List> threeSum(int[] nums, int i, int target) {
        ArrayList> res = new ArrayList>();
        for(int j = i + 1; j < nums.length - 2; j++){
            if(j > i + 1 && nums[j] == nums[j-1]) continue;
            List> curr = twoSum(nums, i, j, target - nums[j]);
            res.addAll(curr);
        }
        return res;
    }
    
    private ArrayList> twoSum(int[] nums, int i, int j, int target){
        int left = j + 1, right = nums.length - 1;
        ArrayList> res = new ArrayList>();
        while(left < right){
            if(nums[left] + nums[right] == target){
                ArrayList curr = new ArrayList();
                curr.add(nums[i]);
                curr.add(nums[j]);
                curr.add(nums[left]);
                curr.add(nums[right]);
                res.add(curr);
                do {
                    left++;
                }while(left < nums.length && nums[left] == nums[left-1]);
                do {
                    right--;
                } while(right >= 0 && nums[right] == nums[right+1]);
            } else if (nums[left] + nums[right] > target){
                right--;
            } else {
                left++;
            }
        }
        return res;
    }
}

3Sum Closet

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

雙指針法 復(fù)雜度

時(shí)間 O(N^2) 空間 O(1)

思路

和3Sum的解法一樣。在3Sum中，我們只有找到和目標(biāo)完全一樣的時(shí)候才返回，但在Closet中，我們要記錄一個(gè)最小的差值，并同時(shí)記錄下這個(gè)最小差值所對(duì)應(yīng)的和。

代碼

public class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int closetSum = 0, minDiff = Integer.MAX_VALUE / 2;
        for(int i = 0; i < nums.length; i++){
            int left = i + 1, right = nums.length - 1;
            while(left < right){
                // 當(dāng)前組合的和
                int sum = nums[i] + nums[left] + nums[right];
                // 當(dāng)前組合的和與目標(biāo)的差值
                int diff = Math.abs(sum - target);
                // 如果差值更小則更新最接近的和
                if(diff < minDiff){
                    closetSum = sum;
                    minDiff = diff;
                }
                // 雙指針的移動(dòng)方法和3Sum一樣
                if (sum < target){
                    left++;
                } else if (sum > target){
                    right--;
                } else {
                    return sum;
                }
            }
        }
        return closetSum;
    }
}