双指针

15. 三数之和【中等】

/*
特判，对于数组长度 n，如果数组为 null 或者数组长度小于3，返回[]。
对数组进行排序,遍历排序后数组：
若 nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于 0，直接返回结果。
对于重复元素：跳过，避免出现重复解
令左指针 L=i+1，右指针 R=n-1，当 L<R时，执行循环：
当 nums[i]+nums[L]+nums[R]==0，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 L,R移到下一位置，寻找新的解
若和大于 0，说明 nums[R]太大，R 左移
若和小于 0，说明 nums[L]太小，L 右移
*/

func threeSum(nums []int) [][]int {
   var ans [][]int
   if len(nums) < 3 {
      return nil
   }

   sort.Ints(nums)
   fmt.Println(nums)
   for i := range nums {
      if nums[i] > 0 { // 因为数组已经排序好，所以nums[i]>0后，就肯定不能相加等于0了
         break
      }

        if i > 0 && nums[i] == nums[i-1] { // 去重，比如[-1,-1,0,1]  只要一个[-1,0,1]即可，却不能是num[i]==num[i+1],比如[-1,-1,2]就会被筛出了
            continue
        }

      left := i + 1 // 这个一定要注意下，因为是从i+left+right，left必须从i+1后开始
      right := len(nums) - 1
      for left < right { // left不可以等于right
         sum := nums[i] + nums[left] + nums[right]
         if sum == 0 {
            res := []int{nums[i], nums[left], nums[right]}

            fmt.Println(i, left, right)

            ans = append(ans, res)
            // 需要将left < right 写在 && 的左边 先行判断, 因为&&有短路求值的特性
            for left < right && nums[left] == nums[left+1] {
               left++
            }
            for left < right && nums[right] == nums[right-1] {
               right--
            }
            left++
            right--
         } else if sum > 0 {
            right--
         } else if sum < 0 {
            left++
         }
      }

   }

   //a := make([][]int)
   //for i := 0; i < len(nums); i++ {
   // for j := i + 1; j < len(nums); j++ {
   //    for k := i + 2; k < len(nums); k++ {
   //       if nums[i]+nums[j]+nums[k] == 0 {
   //
   //       }
   //    }
   // }
   //}
   return ans
}

18. 四数之和【中等】

func fourSum(nums []int, target int) [][]int {

   var ans [][]int
   if len(nums) < 4 {
      return nil
   }

   sort.Ints(nums)
   fmt.Println(nums)

   for first := 0; first < len(nums)-3; first++ {
      if first > 0 && nums[first] == nums[first-1] { // 去重
         continue
      }
      for second := first + 1; second < len(nums)-2; second++ {
         if second > first+1 && nums[second] == nums[second-1] {
            continue
         }

         third := second + 1 //
         fourth := len(nums) - 1

         for third < fourth { // left不可以等于right
            sum := nums[first] + nums[second] + nums[third] + nums[fourth]
            if sum == target {
               res := []int{nums[first], nums[second], nums[third], nums[fourth]}

               fmt.Println(first, second, third, fourth)

               ans = append(ans, res)
               // 需要将left < fourth 写在 && 的左边 先行判断, 因为&&有短路求值的特性
               for third < fourth && nums[third] == nums[third+1] {
                  third++
               }
               for third < fourth && nums[fourth] == nums[fourth-1] {
                  fourth--
               }
               third++
               fourth--
            } else if sum > target {
               fourth--
            } else if sum < target {
               third++
            }
         }
      }
   }

   return ans
}

1099. 小于 K 的两数之和【简单】

给你一个整数数组 nums 和整数 k ，返回最大和 sum ，满足存在 i < j 使得 nums[i] + nums[j] = sum 且 sum < k 。如果没有满足此等式的 i,j 存在，则返回 -1 。

输入：nums = [34,23,1,24,75,33,54,8], k = 60
输出：58
解释：
34 和 24 相加得到 58，58 小于 60，满足题意。

func twoSumLessThanK(nums []int, k int) int {
   if len(nums) <= 1 {
      return -1
   }
   sort.Ints(nums)

   left, right := 0, len(nums)-1
   sum := -1
   for left < right {
      if nums[left]+nums[right] < k {
         sum = max(sum, nums[left]+nums[right])
         left++
      } else {
         right--
      }
   }
   return sum

}

259. 较小的三数之和【中等】

给定一个长度为 n 的整数数组和一个目标值 target ，寻找能够使条件 nums[i] + nums[j] + nums[k] < target 成立的三元组 i, j, k 个数（0 <= i < j < k < n）。

输入: nums = [-2,0,1,3], target = 2

输出: 2

解释: 因为一共有两个三元组满足累加和小于 2: [-2,0,1][-2,0,3]

输入: nums = [], target = 0

输出: 0

输入: nums = [0], target = 0

输出: 0

870. 优势洗牌【中等】

26. 删除有序数组中的重复项【简单】

27. 移除元素【简单】

283. 移动零【简单】

11. 盛最多水的容器【中等】

// ===== 解答：找出两条线，和x轴构成的容器容纳最多的水 ======
func maxArea(height []int) int {
    left, right := 0, len(height)-1
    res := 0
    area := 0
    for left < right {
        area = (right - left) * int(math.Min(float64(height[left]), float64(height[right])))
        res = max(res, area)
        if height[left] < height[right] {
            left++
        } else {
            right--
        }
    }
    return res
}

42. 接雨水【困难】