15 3Sum

忘是亡心i 2022-08-10 00:51 163阅读 0赞

与之类似的题目有  
[1 TwoSum][]  
[16 3Sum Closest][]  
[18 4Sum][]

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    public class No15 { 
    
        public static void main(String[] args) {
            int[] nums = { -1, 0, 1, 2, -1, -4 };
            System.out.println(threeSum(nums));
        }
    
        public static List<List<Integer>> threeSum(int[] nums) {
    
            Arrays.sort(nums);
            List<List<Integer>> result = new ArrayList<List<Integer>>();
    
            for (int i = 0; i < nums.length; i++) {
                int k = i + 1;
                int l = nums.length - 1;
    
                if (nums[i] > 0)   //原先没有这两句，超时，加上这两个if后就不超时了
                    break;
                if (i > 0 && nums[i] == nums[i - 1])
                    continue;
    
                while (k < l) {
                    int sum = nums[i] + nums[k] + nums[l];
                    if (sum < 0)
                        k++;
                    else if (sum > 0)
                        l--;
                    else {
                        List<Integer> list = new ArrayList<Integer>();
                        list.add(nums[i]);
                        list.add(nums[k]);
                        list.add(nums[l]);
                        if (!result.contains(list))
                            result.add(list);
                        k++;
                        l--;
                    }
                }
            }
            return result;
        }
    }

[1 TwoSum]: http://blog.csdn.net/taoxiuxia/article/details/46426585
[16 3Sum Closest]: http://blog.csdn.net/taoxiuxia/article/details/49686639
[18 4Sum]: http://blog.csdn.net/taoxiuxia/article/details/49680349