LeetCode 15. 三数之和

た入场券 2022-10-30 15:24 30阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]

//写法一
    //排序。 第一层循环固定a, 第二层固定b ，c从尾部向左逼近
    class Solution {
        
        public List<List<Integer>> threeSum(int[] nums) {
        
            int n = nums.length;
            Arrays.sort(nums);
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            for(int first = 0; first < n; first++){
        
                if(first == 0 || nums[first] != nums[first - 1]){
        
                    int third = n - 1;
                    int target = -nums[first];
                    for(int second = first + 1; second < n; second++){
        
                        if(second == first + 1 || nums[second] != nums[second - 1]){
        
                            while(second < third && nums[second] + nums[third] > target)
                                --third;
                            if(second == third)
                                break;
                            if(nums[second] + nums[third] == target){
        
                                List<Integer> list = new ArrayList<Integer>();
                                list.add(nums[first]);
                                list.add(nums[second]);
                                list.add(nums[third]);
                                res.add(list);
                            }
                        }
                    }
                }
            }
            return res;
        }
    }

//写法二
    //排序。 第一层循环固定a, b 和 c分别有两个指针指向两边，往里逼近
    class Solution {
        
        public List<List<Integer>> threeSum(int[] nums) {
        
            int n = nums.length;
            Arrays.sort(nums);
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            for(int first = 0; first < n; first++){
        
                if(first == 0 || nums[first] != nums[first - 1]){
        
                    int third = n - 1;
                    int target = -nums[first];
                    int second = first + 1;
                    while(second < third){
        
                        int sum = nums[second] + nums[third];
                        if(sum == target){
        
                            res.add(Arrays.asList(nums[first], nums[second], nums[third]));
                            while(second < third && nums[second] == nums[second + 1])
                                ++second;
                            ++second;
                            while(second < third && nums[third] == nums[third - 1])
                                --third;
                            --third;
                        }else if(sum < target){
        
                            second++;
                        }else{
        
                            third--;
                        }
                    }
                }
            }
            return res;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]: /images/20221024/ab4f5913eee844809a6ce6ac792e6ef3.png