日升时奋斗，日落时自省
目录
一、移动零
二、盛水最多的容器
三、快乐数
四、复写零
五、三数之和
六、有效三角形的个数
七、四数之和
一、移动零
题目来源：. - 力扣（LeetCode）
题目主要内容就是将数组中所有的零移动到最左边
使用快慢指针方法进行处理
代码：
public void moveZeroes(int[] nums) {
for(int cur=0;dest=-1;cur<nums.length;cur++){
if(nums[cur]!=0){
//在判定当前值不等于 0 dest就可以进行加加
dest++;
//进行值的替换
int tmp = nums[cur];
nums[cur]=nums[dest];
nums[dest]=tmp;
}
}
}二、盛水最多的容器
题目来源：. - 力扣（LeetCode）
题目主要内容横坐标的差值为长度，纵坐标的两个最小值为宽度，就散长方形的面积最大
代码：
public int maxArea(int[] height) {
int left = 0 , right = height.length-1 ,ret=0;
while(left<right){
//计算面积
int v = Math.min(height[left],height[right])*(right-left);
//取最大值
ret= Math.max(ret,v);
//进行位置调节
if(height[left]<height[right]){
left++;
}else{
right--;
}
}
return ret;
}三、快乐数
题目来源：. - 力扣（LeetCode）
题目主要内容重复每个位的数进行平方相加==0为快乐数
代码：
//计算数值个位的平方和
public int bigSum(int t){
int sum=0;
while(t>0){
int tmp= t%10;
sum+=tmp*tmp;
t/=10;
}
return sum;
}
public boolean isHappy(int n) {
//第一个和第二个不同
int slow = n, fast = bigSum(n);
while(slow!=fast){
//走一步
slow=bigSum(slow);
//快指针走两步
fast=bigSum(bigSum(fast));
}
return slow==1;
}四、复写零
题目来源：. - 力扣（LeetCode）
题目主要内容每次遇到0就复写一次，后面数值向后移动，末尾数值因为数组大小不变就消失了
上图没有画完，一次类推可以得出结果
注：那当前假设的位置怎么找，这里再配一张图解释
边界情况：
代码：
public void duplicateZeros(int[] nums) {
int cur= 0 , dest = -1 , n=nums.length;
//先去找假设值
while(cur<n){
if(nums[cur]!=0){
dest++;
}else{
dest+=2;
}
if(dest>=n-1)break;
cur++;
}
//越界判断
if(dest==n){
nums[n-1]=0;
cur--;
dest-=2;
}
//复写零
while(cur>0){
if(nums[cur]!=0){
nums[dest--]=nums[cur--];
}else{
nums[dest--]=0;
nums[dest--]=0;
cur--;
}
}
}五、三数之和
题目来源：. - 力扣（LeetCode）
题目主要内容数组中任意三个数和等于target记录下来即可
暴力解法：三个for循环进行遍历就可以解决，当然时间复杂度太高
题解思路：
因为给的数组是无序的，要是使用双指针的话不确定因素太多（就是控制不了数值总和的大小）
首先给数组排个序Java调用库函数就可以排序了
代码：
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ret=new ArrayList<>();
//进行排序
Arrays.sort(nums);
int n=nums.length;
for(int i=0;i<n;){
if(nums[i]>0)break;
int left = i + 1;
int right = n-1;
while(left<right){
//求和
int sum = nums[i]+nums[left]+nums[right];
//小于说明left值太小 向后取更大的
if(sum<0){
left++;
//大于说明right值太大 向前取更小的
}else if(sum>0){
right--;
}else{
//等于就添加进集合中 同时跳过两个位置
ret.add(new ArrayList<>(Arrays.asList(nums[i],nums[left],nums[right])));
right--;
left++;
//左去重
while(left<right&&nums[left]==nums[left-1]){
left++;
}
//右去重
while(left<right&&nums[right]==nums[right+1]){
right--;
}
}
}
i++;
//第一个数去重
while(i<n&&nums[i]==nums[i-1]){
i++;
}
}
return ret;
}六、有效三角形的个数
题目来源：. - 力扣（LeetCode）
题目主要内容计算有效三角形的个数
三角形满足两小边之和大于第三边
如何知道那两个边是小的 ，这里就可以进行排序使用双指针解决问题
最大边就是右边的值
代码：
public int triangleNumber(int[] nums) {
if(nums.length<3){
return 0;
}
Arrays.sort(nums);
int ret=0;
for(int i=nums.length-1;i>=2;i--){
int left = 0, right =i-1;
int maxnum=nums[i];
//双指针移动
while(left<right){
if(nums[left]+nums[right]>maxnum){
//可以跳过当前值
ret+=right-left;
right--;
}else{
//如果针对以上的不满足的 说明值是太小的，left进行++
left++;
}
}
}
return ret;
}七、四数之和
题目来源：. - 力扣（LeetCode）
题目主要内容类似与三数之和，多嵌套一层for循环进行计算，就是固定两个数字不变其他的两个数字称为双指针进行移动
代码：
public List<List<Integer>> fourSum(int[] nums, int target) {
if(nums.length<4){
return new ArrayList<>();
}
List<List<Integer>> ret=new ArrayList<>();
int n=nums.length;
//进行排序 为了 双指针 在计算的时候可以决定总和的大小
Arrays.sort(nums);
for(int i=0;i<n;){
for(int j=i+1;j<n;){
int left = j+1;
int right = n-1;
while(left<right){
if(nums[i]+nums[j]+nums[left]+nums[right]<target){
left++;
}else if(nums[i]+nums[j]+nums[left]+nums[right]>target){
right--;
}else{
ret.add(new ArrayList<>(Arrays.asList(nums[i],nums[j],nums[left],nums[right])));
left++;
right--;
//双指针去重
while(left<right&&nums[left]==nums[left-1]){
left++;
}
while(left<right&&nums[right]==nums[right+1]){
right--;
}
}
}
//第二个数字的去重
j++;
while(j<n&&nums[j]==nums[j-1]){
j++;
}
}
//第一个数字的去重
i++;
while(i<n&&nums[i]==nums[i-1]){
i++;
}
}
return ret;
}
