By

Contents
  1. 1. Two Sum
  2. 2. Three Sum
  3. 3. Four Sum
  4. 4. 寻找和为定值的多个数

此类算法类似于0-1背包问题。

Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution.

Example:
    Given nums = [2, 7, 11, 15], target = 9,
    Because nums[0] + nums[1] = 2 + 7 = 9,
    return [0, 1].

1
2
3
4
5
6
7
8
9
10
11
12
public int[] twoSum(int[] nums, int target){
    int[] res = new int[2];
    HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
    for(int i = 0; i<nums.length; i++){
        if(map.containsKey(target-nums[i])){
            res[1] = i;
            res[0] = map.get(target-nums[i]);
        }
        map.put(nums[i],i);
    }
    return res;
}

Three Sum

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//设置两个指针，用O(n^2)时间复杂度
public  List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>>  res = new ArrayList<List<Integer>>();
    //边界情况
    int n = nums.length;
    if(n<3 || nums==null) return res;
    //为了防止重复，先排个序
    Arrays.sort(nums);
    for(int i=0; i<n-1 ;i++){
        //处理i可能出现的重复
        if(i==0 || nums[i]>nums[i-1]){
            int j=i+1;
            int k=n-1;
            
            while(j<k){
                if(nums[i]+nums[j]+nums[k]==0 && j<k){
                    List<Integer> l = new ArrayList<Integer>(); 
                    l.add(nums[i]);
                    l.add(nums[j]);
                    l.add(nums[k]);
                    res.add(l);
                    //继续更新两个指针
                    j++;
                    k--; 
                    //处理一下j k的重复问题
                    while(j<k && nums[j]==nums[j-1]) j++;
                    while(j<k && nums[k]==nums[k+1]) k--;
                }else if(nums[i]+nums[j]+nums[k]<0){
                    j++;
                }else{
                    k--;
                }
            }
        }
        
    }
    return res;
}

Four Sum

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
26
27
28
29
30
31
32
33
34
35
36
37
//思路，跟前面的3sum一致,可以总结出规律
public List<List<Integer>> fourSum(int[] nums, int target) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    int n = nums.length;
    if(nums == null || n<4) return res;
    //先排序
    Arrays.sort(nums);
    for(int i = 0 ; i < n-1; i++ ){
        //筛掉重复的
        if(i!=0 && nums[i-1]==nums[i]) continue;
        for(int j=i+1; j<n ; j++){
            //筛掉重复的
            if(j!=i+1 && nums[j-1]==nums[j]) continue;
            int k = j+1;
            int l = n-1;
            while(k<l){
                if(nums[i]+nums[j]+nums[k]+nums[l]==target){
                    ArrayList<Integer> list = new ArrayList<Integer>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(nums[k]);
                    list.add(nums[l]);
                    res.add(list);
                    k++;
                    l--;
                    //筛掉重复的
                    while(nums[k-1]==nums[k] && k<l) k++;
                    while(nums[l+1]==nums[l] && k<l) l--;
                }else if(nums[i]+nums[j]+nums[k]+nums[l]<target) k++;
                else if(nums[i]+nums[j]+nums[k]+nums[l]>target) l--;
            }
        }
    }
    return res;
    
}

寻找和为定值的多个数

输入两个整数n和sum，从数列1，2，3…….n 中随意取几个数，使其和等于sum，要求将其中所有的可能组合列出来。

注意到取n，和不取n个区别即可，考虑是否取第n个数的策略，可以转化为一个只和前n-1个数相关的问题。
如果取第n个数，那么问题就转化为“取前n-1个数使得它们的和为sum-n”，对应的代码语句就是sumOfkNumber(sum - n, n - 1)；
如果不取第n个数，那么问题就转化为“取前n-1个数使得他们的和为sum”，对应的代码语句为sumOfkNumber(sum, n - 1)。

Contents
  1. 1. Two Sum
  2. 2. Three Sum
  3. 3. Four Sum
  4. 4. 寻找和为定值的多个数