双指针

两数之和

click here for leetcode detail

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        if (numbers == null || numbers.length == 0){
            return new int[]{-1};
        }
        int start = 0;
        int end = numbers.length-1;
        for (int i = 0; i < numbers.length; i++){
            if (numbers[start] + numbers[end] == target){
                return new int[]{start, end};
            }
            if(numbers[start] + numbers[end] > target){
                end--;
            }
            if(numbers[start] + numbers[end] < target){
                start++;
            }
        }
        return new int[]{-1}; 
    }
}

三数之和

click here for leetcode detail

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        if ( nums == null || nums.length < 3){
            return new ArrayList();
        }
        //排序，例如快排的时间复杂度为nlogn
        Arrays.sort(nums); 
        Set<List<Integer>> result = new HashSet();
        for (int i = 0; i < nums.length - 1; i++){
            int mid = i + 1;
            int end = nums.length - 1;
            for (int j = i + 1; j < nums.length - 1; j++){
                if(nums[i] + nums[end] + nums[mid] == 0 && end > mid){
                    List<Integer> resultEx = new ArrayList();
                    resultEx.add(nums[I]);
                    resultEx.add(nums[mid]);
                    resultEx.add(nums[end]);
                    result.add(resultEx);
                    //这里需要变化mid，不然下一轮for循环i、mid、end都没有变化，会重复记录结果
                    mid++;
                } 
                if (nums[i] + nums[end] + nums[mid] > 0 ){
                    end--;
                }
                if (nums[i] + nums[end] + nums[mid] < 0 ){
                    mid++;
                }
            }
        }
        return new ArrayList(result);
    }
}

直方图的水量

click here for leetcode detail
给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。

示意图

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的直方图，在这种情况下，可以接 6 个单位的水（蓝色部分表示水）。 感谢 Marcos 贡献此图。

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

class Solution {
    public int trap(int[] height) {
        if(height == null || height.length == 0){
            return 0;
        }
        //层高，从1开始
        int maxHeight = getMax(height);
        //水量
        int sum = 0;
        //floor为层高
        for (int floor = 1; floor <= maxHeight; floor++){
        //获取当前高度第一个直方格位置和最后一个直方格位置
        int start = getStart(height, floor);
        int end = getEnd(height, floor);
            for(int i = start; i <= end; i++){
                if (height[i] <= floor - 1){
                    sum++;
                }
            }
        }
        return sum;
    }
    private int getMax(int[] height){
        int max = 0;
        for(int i = 0; i < height.length - 1; i++){
            if (height[i] > max){
                max = height[I];
            }
        }
        return max;
    }
    private int getStart(int[] height, int floor){
        for(int i = 0; i < height.length - 1; i++){
            if (height[i] >= floor){
                return I;
            }
        }
        return 0;
    }
    private int getEnd(int[] height, int floor){
        for(int i = height.length - 1; i >= 0; i--){
            if (height[i] >= floor){
                return I;
            }
        }
        return 0;
    }
}