167. 两数之和 II (opens new window)

有序数组

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int l = 0,r = numbers.length-1;
        while(l<=r){
            int sum = numbers[l]+numbers[r];
            if(target == sum){
                return new int[]{l+1,r+1};
            }else if(target<sum){
                r--;
            }else{
                l++;
            }
        }
        return new int[]{-1,-1};
    }
}

611. 有效三角形的个数 (opens new window)

15. 三数之和 (opens new window)

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            if(nums[i]>0) return res;
            if(i>0 && nums[i]==nums[i-1]) continue;
            int l=i+1,r=nums.length-1;
            while(l<r){
                int sum = nums[i]+nums[l]+nums[r];
                if(sum>0) r--;
                else if(sum<0) l++;
                else{
                    res.add(Arrays.asList(nums[i],nums[l],nums[r]));
                    while(r>l && nums[r]==nums[r-1]){
                        r--;
                    }
                    while(r>l && nums[l]==nums[l+1]){
                        l++;
                    }
                    l++;
                    r--;
                }
            }
        }
        return res;
    }
}

11. 盛最多水的容器 (opens new window)

class Solution {
    public int maxArea(int[] height) {
        int ans = 0;
        int l=0,r=height.length-1;
        int area = 0;
        while(l<r){
            area = (r-l) * Math.min(height[l],height[r]);
            ans = Math.max(ans,area);
            if(height[l]<height[r]){
                l++;
            }else{
                r--;
            }
        }
        return ans;
    }
}

42. 接雨水 (opens new window)

方法一：前后缀数组

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int[] preMax = new int[n];
        int[] sufMax = new int[n];
        preMax[0] = height[0];
        for(int i=1;i<n;i++){
            preMax[i] = Math.max(preMax[i-1],height[i]);
        }
        sufMax[n-1] = height[n-1];
        for(int i=n-2;i>=0;i--){
            sufMax[i] = Math.max(sufMax[i+1],height[i]);
        }
        int ret = 0;
        for(int i=0;i<n;i++){
            ret += Math.min(preMax[i],sufMax[i])-height[i];
        }
        return ret;
    }
}

方法二：双指针

class Solution {
    public int trap(int[] height) {
        int l=0,r=height.length-1,ans=0;
        int preMax = 0;
        int sufMax = 0;
        while(l<=r){
            preMax = Math.max(preMax,height[l]);
            sufMax = Math.max(sufMax,height[r]);
            if(preMax<sufMax){
                ans += preMax-height[l++];
            }else{
                ans += sufMax-height[r--];
            }
        }
        return ans;
    }
}

581. 最短无序连续子数组 (opens new window)

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        if(isSorted(nums)) return 0;
        int[] numsSorted = new int[nums.length];
        System.arraycopy(nums,0,numsSorted,0,nums.length);
        Arrays.sort(numsSorted);
        int l=0;
        while(nums[l] == numsSorted[l]){
            l++;
        }
        int r=nums.length-1;
        while(nums[r] == numsSorted[r]){
            r--;
        }
        return r-l+1;
    }
    boolean isSorted(int[] nums){
        for(int i=1;i<nums.length;i++){
            if(nums[i]<nums[i-1]){
                return false;
            }
        }
        return true;
    }
}

633. 平方数之和 (opens new window)

31. 下一个排列 (opens new window)

1. 从后往前找第一个比自己后一位小的元素，确定其索引 i ;

2. 从后往前找第一个比nums[i]大的元素下标 j ；

3. 交换两个位置元素；

4. 翻转 i+1 到 n-1的元素；

案例：

nums = [1,2,7,4,3,1]

1. 倒序遍历找到第一组 前一个数比后一个数小的两个数 [2,7]，索引为1；
2. 从[7,4,3,1]中从后往前中找出比2大的第一个数：3，索引为j；
3. 交换后：[1,3,7,4,2,1]；
4. 对3后面的数翻转：[1,3,1,2,4,7]；

class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int i = n-2;
        while(i>=0){
            if(nums[i]<nums[i+1])
                break;
            i--;
        }
        if(i>=0){
            int j = n-1;
            while(j>=0){
                if(nums[j]>nums[i]){
                    break;
                }
                j--;
            }
            swap(nums,i,j);
        }
        rev(nums,i+1,n-1);
    }
    void rev(int[] nums,int l,int r){
        while(l<r){
            swap(nums,l,r);
            l++;r--;
        }
    }
    void swap(int[] nums,int l,int r){
        int tmp = nums[l];
        nums[l] = nums[r];
        nums[r] = tmp;
    }
}