记录刷题过程。

双指针

这里的双指针我理解的是从两端开始，从而减少循环次数。一般我们循环都是从某一个端点移向另一个端点，如果从两端向中间移动，有点分而治之的思想在里面。例如当你要遍历数组时，正常都是用 for 循环遍历：

for(int i=0; i<arr.length; i++) {
    sout(arr[i]);
}

但是用双指针，就从两边开始，会快很多：

// 这里数组arr长度是偶数
int i=0,j=arr.length -1;
while (i<j){
    System.out.println(arr[i]);
    System.out.println(arr[j]);
    i++;
    j--;
}

具体在题目中的应用：

题目：盛最多水的容器

链接：https://leetcode-cn.com/problems/container-with-most-water/

用暴力破解法：

public static int f1(int[] nums) {
    int r = 0;
    for (int i = 0; i < nums.length; i++) {
        for (int j = i+1; j < nums.length; j++) {
            // i = x1, j = x2 , nums[i] = y1, nums[j] = y2
            int x = j - i;
            int y = Math.min(nums[i],nums[j]);
            r = Math.max(r,x*y);
        }
    }
    return r;
}

用双指针：

public static int f2(int[] nums) {
    int r = 0,i = 0,j = nums.length-1;
    while (i < j) {
        if (nums[i] > nums[j]) {
            r =  Math.max(r,(j - i) * nums[j--]);
        }else {
            r = Math.max(r,(j - i) * nums[i++]);
        }
    }
    return r;
}