【每日一题Day260】LC15三数之和 | 排序 + 双指针

三数之和【LC15】

给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != ji != kj != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

**注意:**答案中不可以包含重复的三元组。

排序+双指针

  • 思路

    • 首先对数组进行排序,然后遍历数组,在确定nums[i]的情况下,在数组nums[i+1,n-1]中使双指针法(前后指针),确定另外两个元素,判断这三个元素之和sumtarget的大小:
      • 如果

        s

        u

        m

        >

        t

        a

        r

        g

        e

        t

        sum>target

        sum>target,左移左指针,使sum减小

      • 如果

        s

        u

        m

        <

        t

        a

        r

        g

        e

        t

        sum<target

        sum<target,右移右指针,使sum增大

      • 如果

        s

        u

        m

        =

        =

        t

        a

        r

        g

        e

        t

        sum==target

        sum==target,添加三元组至结果集

    • 去重

      • 在找到符合条件的三元组后,移动指针r、l跳过相同元素,以便过滤掉重复的三元组
      • 如果nums[i]==nums[i-1]

        n

        u

        m

        s

        [

        i

        ]

        nums[i]

        nums[i]的三元组是

        n

        u

        m

        s

        [

        i

        1

        ]

        nums[i-1]

        nums[i1]的子集,需要跳过

      • 在遇到不符合条件的左右边界时也可以移动双指针去重,但是由于根据sum和target的大小关系,双指针也会被移动,所以此时是否去重不是必须的
  • 实现

    1. 首先将数组排序;

    2. 然后有一层for循环,

      i

      i

      i从下表0的地方开始,同时定义下标left在i+1位置上,定义下标right在数组末尾的位置上

    3. 如果nums[i]>0,不可能存在三元组,直接退出循环,返回结果集

    4. 去重:如果(i > 0 && nums[i] == nums[i - 1])

      n

      u

      m

      s

      [

      i

      ]

      nums[i]

      nums[i]的三元组是

      n

      u

      m

      s

      [

      i

      1

      ]

      nums[i-1]

      nums[i1]的子集,需要跳过

    5. 移动left和right

      • 如果nums[i] + nums[left] + nums[right] > 0,说明right下标应该向左移动

        去重:while (left < right && nums[right] == nums[right + 1]) right--;【非必须】

      • 如果nums[i] + nums[left] + nums[right] < 0,说明left下标应该向右移动

        去重: while (left < right && nums[left] == nums[left - 1]) left++;【非必须】

      • 如果nums[i] + nums[left] + nums[right] == 0,说明找到了三元组,双指针同时收缩,right--;left++

        去重: while (right > left && nums[right] == nums[right - 1]) right--;
        while (right > left && nums[left] == nums[left + 1]) left++;

      class Solution {
          public List<List<Integer>> threeSum(int[] nums) {
              List<List<Integer>> res = new ArrayList<>();
              Arrays.sort(nums);
              for (int i = 0; i < nums.length - 2; i++){
                  if (nums[i] > 0){
                      return res;
                  }
                  if (i > 0 && nums[i] == nums[i-1] ){
                      continue;
                  }
                  int left = i + 1;
                  int right = nums.length - 1;
                  while (left < right){
                      int sum = nums[i] + nums[left] + nums[right];
                      if (sum > 0){
                          right--;
                          // 非必须
                          while(left < right && nums[right] == nums[right+1]){
                              right--;
                          }
                      }else if (sum < 0){
                          // 非必须
                          left++;
                          while (left < right && nums[left-1] == nums[left]){
                              left++;
                          }
                      }else{
                          res.add(Arrays.asList(nums[i],nums[left],nums[right]));
                          while(left < right && nums[right] == nums[right-1]){
                              right--;
                          }
                          while (left < right && nums[left+1] == nums[left]){
                              left++;
                          }
                          right--;
                          left++;
                      }
                  }
              }
              return res;
          }
      }
      
      class Solution {
          public List<List<Integer>> threeSum(int[] nums) {
              Arrays.sort(nums);
              List<List<Integer>> res = new ArrayList<>();
              int len = nums.length;
              int i  = 0;
              while (i < len - 2){
                  twoSum(nums,i,res);
                  int temp = nums[i];
                  while (i < len && temp == nums[i]){
                      i++;
                  }
              }
              return res;
          }
          public void twoSum(int[] numbers, int i, List<List<Integer>> res ) {
              int len = numbers.length;
              int left = i + 1;
              int right = len - 1;
              while(left < right){
                  if ( numbers[i] + numbers[left] + numbers[right] == 0){
                      res.add(Arrays.asList(numbers[i],numbers[left],numbers[right]));
                      int temp = numbers[left];
                      while (numbers[left] == temp && left < right){
                          left++;
                      }
                  }else if(numbers[i] + numbers[left] + numbers[right] > 0){
                      right--;
                  }else {
                      left++;
                  }
              }
          }
      }
      
      • 复杂度

        • 时间复杂度:

          O

          (

          n

          l

          o

          g

          n

          +

          n

          2

          )

          O(nlogn+n^2)

          O(nlogn+n2),其中 n是数组的长度。排序所需的时间复杂度一般为

          O

          (

          n

          l

          o

          g

          n

          )

          O(nlogn)

          O(nlogn),查找三元组的时间复杂度为

          O

          (

          n

          2

          )

          O(n^2)

          O(n2),因此时间复杂度为

          O

          (

          n

          2

          )

          O(n^2)

          O(n2)

        • 空间复杂度:

          O

          (

          1

          )

          O(1)

          O(1)

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>