移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]
输出: [0]
思路：使用快慢指针，初始都指向第一个元素
如果元素为0，快指针向后移动一位
如果元素不为0，慢指针赋值为快指针所指元素，快慢指针同时后移
最后从slow指针开始，为末尾元素赋值0
class Solution {
public void moveZeroes(int[] nums) {
int slow =0;
int fast = 0;
int len = nums.length;
for(int i = 0;i < len;i++){
if(nums[i] == 0){
fast ++;
}
else {
nums[slow++]=nums[fast++];
}
} for(int i = slow; i < len;i++){
nums[slow++] = 0;
}
}
}
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
fast,slow = 0,0
length = len(nums)
for i in range(length):
if nums[i] != 0:
nums[slow] = nums[fast]
slow+=1
fast+=1
for i in range(slow,length):
nums[i] = 0;
盛最多的水
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
思路：两条线i，j储水量为min(height(i),height(j))*(j-i),可以使用暴力枚举法，计算每两条线段的储水量，再取最大值
class Solution {
// 两条线i，j储水量为min(height(i),height(j))*(j-i),
// 可以使用暴力枚举法，计算每两条线段的储水量，再取最大值
public int maxArea(int[] height) {
int len = height.length;
int area = 0;
int maxArea = 0;
for(int i = 0 ; i < len;i++){
for(int j = i +1 ;j<len;j++){
area = Math.min(height[i], height[j]) * (j-i);
maxArea = Math.max(area,maxArea);
}
}
return maxArea;
}
}但是使用暴力法，会出现超时
思路：使用双指针法。left指向第一个元素，right指向最后一个元素。
两条线left，right储水量为min(height(right),height(left))*(right-left)
由公式可知为了寻找更大容量的储水量，应该增大min(height(right),height(left))，如果移动较大的指针 min(height(right),height(left))保持不变，只有移动较小的指针才能存在增大容量的可能性
public int maxArea(int[] height){
int left = 0;
int right = height.length-1;
int area = 0;
int maxArea = 0;
while (left < right){
area = Math.min(height[left],height[right]) * (right-left);
maxArea = Math.max(area,maxArea);
if(height[left] <= height[right])
left++;
else
right--;
}
return maxArea;
}python
class Solution:
def maxArea(self, height: List[int]) -> int:
left = 0
right = len(height)-1
area,maxArea = 0,0
while(left < right):
area = min(height[left],height[right]) * (right-left)
maxArea = max(maxArea,area);
if height[left] <= height[right]:
left+=1
else:
right-=1
return maxArea
三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
思路：最容易想到暴力枚举，三层for循环，判断nums[i] + nums[j] + nums[k] == 0，等于就加入数组
而不能包含重复的三元组，则需要在遍历前对数据进行排序,并且要在每层for循环前判断是否与前一个元素相同去重
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
ArrayList<List<Integer>> lists = new ArrayList<>();
int len = nums.length;
Arrays.sort(nums);
for (int i = 0;i< len; i ++){
//如果与前一个数相同，跳过，避免产生相同的元组
if(i>0 && nums[i] == nums[i-1])
continue;
for (int j = i+1;j< len; j ++){
if(j>i+1 && nums[j] == nums[j-1])
continue;
for (int k = j+1; k < len; k++) {
if(k>j+1 && nums[k] == nums[k-1])
continue;
if(nums[i] + nums[j] + nums[k] == 0){
ArrayList<Integer> list = new ArrayList<>();
list.add(nums[i]);
list.add(nums[j]);
list.add(nums[k]);
lists.add(list);
}
}
}
}
return lists;
}
}用三层for循环超时了，也可以使用哈希表，但是不太好去重。可以使用双指针
思路：拿这个nums数组来举例，首先将数组排序，然后有一层for循环，i从下标0的地方开始，同时定一个下标left 定义在i+1的位置上，定义下标right 在数组结尾的位置上。
依然还是在数组中找到 abc 使得a + b +c =0，我们这里相当于 a = nums[i]，b = nums[left]，c = nums[right]。
接下来如何移动left 和right呢， 如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。
如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。
java代码
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
ArrayList<List<Integer>> lists = new ArrayList<>();
int length = nums.length;
Arrays.sort(nums);
for (int i = 0; i < length; i++) {
//第一个元素大于0，直接返回
if(nums[0] > 0) return lists;
//对第一个元素去重
if(i > 0 && nums[i] == nums[i-1]) continue;
int left = i +1;
int right = length-1;
while (left < right){
int sum = nums[i] + nums[left] + nums[right];
//大于0，左移
if(sum > 0) right--;
//小于0，右移
else if (sum < 0) left++;
//相等保存结果
else {
lists.add(Arrays.asList(nums[i],nums[left],nums[right]));
//对b，c去重
while (left < right && nums[left+1] == nums[left]) left++;
while (left < right && nums[right-1] == nums[right]) right--;
right--;
left++;
}
}
}
return lists;
}
}python代码
class Solution:
def threeSum(self, nums: list[int]) -> list[list[int]]:
length = len(nums)
lists = []
nums = sorted(nums);
for i in range(length):
if nums[i] > 0 :
return lists
if i > 0 and nums[i] == nums[i-1]:
continue
left = i +1
right = length-1;
while left < right:
sum = nums[i] + nums[left] + nums[right]
if sum > 0:
right-=1
elif sum < 0:
left +=1
else:
l = [nums[i],nums[left],nums[right]]
lists.append(l)
while left < right and nums[left] == nums[left+1]:
left+=1
while left < right and nums[right] == nums[right-1]:
right-=1
left+=1
right-=1
return lists
接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
思路：想象你在数组的任意一个位置 i，这个位置上方能积多少水？首先找到他左边最高的柱子leftmax，然后找到右边最高的柱子rightmax，则位置 i 的积水量为min(leftmax, rightmax) – height[i]。 在双指针法中为什么leftmax<rightmax时就可以确定left处的积水量呢？这是因为此时left的左右屏障都以确定，且左边更短，储水量取决于leftmax，我们不需要知道left右边最高的高度是多少，只知道右边已经有一个比leftmax更高的屏障，确保水不会从右边流走，所以该位置的储水量就是leftmax-height[left]。
java代码
class Solution {
public int trap(int[] height) {
int left = 0;
int right = height.length-1;
int maxLeft = 0;
int maxRight = 0;
int ans = 0;
while (left < right){
maxLeft = Math.max(height[left],maxLeft);
maxRight = Math.max(height[right],maxRight);
if(maxLeft < maxRight)
ans+=maxLeft-height[left++];
else
ans+=maxRight-height[right--];
}
return ans;
}
}