leetcode

[izuomeng]

1. Container With Most Water(题目代号11)

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.
（一堆竖线找能装最多水的两条，返回水量）

答：

暴力穷举会超时，看了官方给的答案后真是太妙了，从数组两端开始，每次算一下当前的水量并维护一个最大值，每次让较短的那条线的指针往里移动，直到两条线碰面为止，AC代码如下：

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    var max = 0,
        i = 0,
        j = height.length - 1
    while(j - i >= 1){
        max = Math.max(Math.min(height[i], height[j]) * (j - i), max)
        height[i] < height[j] ? i++ : j--
    }
    return max
};

2.3Sum(题目代号15)

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

答：

将问题转化一下，其实就是先固定一个数，剩下的就是找两个数，他俩的和为其相反数，这就清晰多了，先把数组排好序，固定的那个数a[i]当然是循环从第一个开始到0结束，因为把负数都找一遍后正数也没必要再找了，找两个和为a[i]的数a[left]和a[right]就一个下标从i+1向后，另一个从len-1向前，如果比a[i]相反数大，说明加多了，要把right减一，否则就把left加一，如果找到相等的，就把三个数推进答案数组，还有最关键的防止TLE的步骤就是如果此时a[left+1]=a[left]，就跳过a[left+1]，right那侧也一样，循环外部的i也同理，这样可以跳过很多重复的搜索，是AC的关键，代码如下

var threeSum = function(nums) {
    var a = nums.sort(function(pre, next){
        return pre - next
    }),
        ans = [],
        target,
        i,
        left,
        right,
        len = nums.length,
        sum,
        index,
        help = []
    for(i = 0; i < len; i++){
        if(a[i] > 0){
            break
        }
        target = -a[i]
        left = i + 1
        right = len - 1
        while(left < right){
            sum = a[left] + a[right]
            if(sum < target){
                left++
            }
            if(sum > target){
                right--
            }
            if(sum === target){
                help = [a[i], a[left], a[right]]
                ans.push(help)
                left++
                right--
                while(a[left] === help[1] && left < right){
                    left++
                }
                while(a[right] === help[2] && left < right){
                    right--
                }
            }
        }
        while(a[i + 1] === help[0] && i < len){
            i++
        }
    }
    return ans
};