［LeetCode］Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,

If n = 4 and k = 2, a solution is:

[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]


解题思路：
                1. 求n个数中的k个数的组合，如果此组合含有n,则就是求n-1的k-1个组合，不含有n，就是n-1的k。即 combine(n, k) = combine(n-1, k -1) + combine(n-1, k);
                2. 要注意的就是n-1,k-1可能返回nil, 那么这时就要初始化n。
       

public List> combine(int n, int k) {
         List> res = new ArrayList>();
         
         if( n < k || k == 0) return res;
         
         res = combine(n-1, k-1);
         
         for(int i = 0; i < res.size(); i++){
             List tmp = res.get(i);
             tmp.add(n);
         }
         
         if(res.size() == 0){
             List tmp = new ArrayList();
             tmp.add(n);
             res.add(tmp);
         }
         
         res.addAll(combine(n-1, k));
         
         return res;
    }

[LeetCode] 3 sum

Question:

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

解题思路：2个pointer，前后扫描。注意移动的时候，要移到下一个不同的数。

Java Code:

public List> threeSum(int[] num) {
        Arrays.sort(num);
        List> res = new ArrayList>();
        
        for(int i = 0; i < num.length - 2;){
            int s = i+1;
            int e = num.length - 1;
            
            while(s < e){
                int total = num[i]+num[s]+num[e];
                if(total == 0){
                    List tmp = new ArrayList();
                    tmp.add(num[i]);
                    tmp.add(num[s]);
                    tmp.add(num[e]);
                    res.add(tmp);
                }
                
                if(total >= 0){
                    e--;
                    while(e > s && num[e+1] == num[e]) e--;
                }
                
                if(total <= 0){
                   s++;
                   while(e > s && num[s] == num[s-1]) s++;
                }
            }
            
            i++;
            while(i < num.length-2 && num[i] == num[i-1]) i++;
        }
        
        return res;
}