双指针

两数平方和：https://leetcode-cn.com/problems/sum-of-square-numbers/

class Solution {
 public boolean judgeSquareSum(int c) {
     //左右指针，左指针0，右指针为c的开平方
     int left = 0;
     int right = (int)Math.sqrt(c);

     while(left <= right){
         //中间值为左的平方 + 右的平方
         int middle = left*left + right*right;
         if(middle < c){
             left++;
         }else if(middle > c){
             right--;
         }else{
             return true;
         }
     }
     return false;
 }
}

盛水容器：https://leetcode-cn.com/problems/container-with-most-water/submissions/

class Solution {
 public int maxArea(int[] height) {
     if(height.length == 0){
         return 0;
     }

     int left = 0;
     int right = height.length-1;

     int result = 0;
     while(left <= right){
         //左比右高，提取右为高，right--。右比左高，提取左为高，left++
         if(height[left] > height[right]){
             int high = height[right];
             int width = right-left;
             result = Math.max(result,high*width);
             right--;
         }else{
             int high = height[left];
             int width = right-left;
             result = Math.max(result,high*width);
             left++;
         }
     }
     return result;
 }
}

三数之和：https://leetcode-cn.com/problems/3sum/

class Solution {
 public List<List<Integer>> threeSum(int[] nums) {

     List<List<Integer>> result = new ArrayList<>();
     if(nums.length == 0){
         return result;
     }

     //排序，后续遍历时，当元素大于0就截止
     Arrays.sort(nums);

     for(int i=0;i<nums.length;i++){
         //如果元素已经大于0，break
         if(nums[i] > 0){
             break;
         }
         //去重
         if(i > 0 && nums[i] == nums[i-1]){
             continue;
         }
         //双指针
         int left = i+1;
         int right = nums.length-1;
         while(left < right){
             int sum = nums[i]+nums[left]+nums[right];
             if(sum == 0){
                 //添加和为0的三个元素
                 result.add(Arrays.asList(nums[i],nums[left],nums[right]));
                 //判断后续重复
                 while(left < right && nums[left] == nums[left+1]){
                     left++;
                 }
                 while(left < right && nums[right] == nums[right-1]){
                     right--;
                 }
                 left++;
                 right--;
             }else if(sum < 0){
                 left++;
             }else if(sum > 0){
                 right--;
             }
         }
     }
     return result;
 }
}

最接近的三数之和：https://leetcode-cn.com/problems/3sum-closest/submissions/

class Solution {
 public int threeSumClosest(int[] nums, int target) {
     //先排序
     Arrays.sort(nums);

     //初始化result为前三个数的和
     int result = nums[0]+nums[1]+nums[2];

     //遍历
     for(int i=0;i<nums.length;i++){
         //双指针
         int left = i+1;
         int right = nums.length-1;
         while(left < right){
             //三数之和
             int sum = nums[i]+nums[left]+nums[right];
             //如果sum和target的差值比result和target的差值小，说明sum的三个值更接近
             if(Math.abs(sum-target) < Math.abs(result-target)){
                 result = sum;
             }else if(sum == target){
                 return result;
             }else if(sum < target){
                 left++;
             }else if(sum > target){
                 right--;
             }
         }
     }
     return result;
 }
}

接雨水：https://leetcode-cn.com/problems/trapping-rain-water/

class Solution {
 public int trap(int[] height) {
     if(height.length == 0){
         return 0;
     }

     //从左往右，存最大值
     int[] left = new int[height.length];
     for(int i=1;i<height.length;i++){
         left[i] = Math.max(left[i-1],height[i-1]);
     }

     //从右往左，存最大值
     int[] right = new int[height.length];
     for(int i=height.length-2;i>=0;i--){
         right[i] = Math.max(right[i+1],height[i+1]);
     }

     int result = 0;
     //从1到height.lengt-2
     for(int i=1;i<height.length-1;i++){
         //提取最小值
         int min = Math.min(left[i],right[i]);
         //如果min比height[i]大，叠加差值
         if(min > height[i]){
             result += min-height[i];
         }
     }
     return result;
 }
}

荷兰国旗：https://leetcode-cn.com/problems/sort-colors/

class Solution {
 public void sortColors(int[] nums) {
     //三指针
     int left = 0;
     int right = nums.length-1;
     int cur = 0;

     while(cur <= right){
         //left控制0，当cur为0时，交换cur和left，因为left已经搜索过了，left++，cur++
         if(nums[cur] == 0){
             int temp = nums[cur];
             nums[cur] = nums[left];
             nums[left] = temp;
             left++;
             cur++;
         }else if(nums[cur] == 2){
             //right控制2，当cur为2时，交换cur和right，因为right未搜索，cur不能++
             int temp = nums[cur];
             nums[cur] = nums[right];
             nums[right] = temp;
             right--;
         }else{
             cur++;
         }
     }
 }
}

移动0：https://leetcode-cn.com/problems/move-zeroes/submissions/

class Solution {
 public void moveZeroes(int[] nums) {
     int left = 0;
     for(int right=0;right<nums.length;right++){
         //不为0时，right和left交换，left++
         if(nums[right] != 0){
             int temp = nums[right];
             nums[right] = nums[left];
             nums[left] = temp;
             left++;
         }
     }
 }
}

寻找重复数(floyd判圈)：https://leetcode-cn.com/problems/find-the-duplicate-number/

class Solution {
 public int findDuplicate(int[] nums) {
     //flyid判圈法，数组模拟链表：fast[nums[fast]]和nums[slow]

     //快慢指针
     int slow = 0;
     int fast = 0;
     slow = nums[slow];
     fast = nums[nums[fast]];

     //寻找重复，快走2慢走1
     while(slow != fast){
         slow = nums[slow];
         fast = nums[nums[fast]];
     }

     //重置快指针，快慢一起走
     fast = 0;
     while(slow != fast){
         slow = nums[slow];
         fast = nums[fast];
     }
     return fast;
 }
}

和为S的连续序列：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/submissions/

class Solution {
public int[][] findContinuousSequence(int target) {
    //使用List暂存
    List<int[]> result = new ArrayList<>();

    //快慢指针，初始为
    int slow = 1;
    int fast = 1;
    int sum = 0;
    //阈值，达到一半即可
    while(slow <= target/2){
        if(sum < target){
            sum += fast;
            fast++;
        }else if(sum > target){
            sum -= slow;
            slow++;
        }else if(sum == target){
            int start = slow;
            int[] temp = new int[fast - slow];
            for(int i=0;i<temp.length;i++){
                temp[i] = start++;
            }
            result.add(temp);
            sum -= slow;
            slow++;
        }
    }
    return result.toArray(new int[result.size()][]);
}
}