content: package question0015_3sum;
  
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.List;
  
  /**
   * 内层循环采用双指针遍历的形式。
   *
   * 时间复杂度是O(n ^ 2)，其中n为nums数组的长度。空间复杂度是O(1)。
   *
   * 执行用时：22ms，击败94.05%。消耗内存：43.9MB，击败98.11%。
   */
  public class Solution {
      public List<List<Integer>> threeSum(int[] nums) {
          List<List<Integer>> result = new ArrayList<>();
          Arrays.sort(nums);
          for (int i = 0; i < nums.length; i++) {
              if (nums[i] > 0) {
                  break;
              }
              if (i > 0 && nums[i] == nums[i - 1]) {
                  continue;
              }
              int target = -nums[i];
              int left = i + 1, right = nums.length - 1;
              while (left < right) {
                  if (nums[left] + nums[right] == target) {
                      result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                      while (left + 1 < right && nums[left + 1] == nums[left]) {
                          left++;
                      }
                      while (right - 1 > left && nums[right - 1] == nums[right]) {
                          right--;
                      }
                      left++;
                      right--;
                  } else if (nums[left] + nums[right] > target) {
                      right--;
                  } else {
                      left++;
                  }
              }
          }
          return result;
      }
  }