双指针
2022-03-07 本文已影响0人
Eden0503
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
}
