Array and Linked List - YonguoS/study_algorithms GitHub Wiki

1. 盛水最多的容器（https://leetcode-cn.com/problems/container-with-most-water/）
   巧用双指针法来避免二重循环：

    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        max_area, l, r = 0, 0, len(height) - 1
        while l < r:
            curr_area = min(height[l], height[r]) * (r - l)
            max_area = max(max_area, curr_area)
            if height[l] > height[r]:
                r -= 1
            else:
                l += 1
        return max_area

2. 移动零（https://leetcode-cn.com/problems/move-zeroes/）
   核心思想是先把非0的元素归位，最后剩余的位置补0即可。

3. 爬楼梯（https://leetcode-cn.com/problems/climbing-stairs/）
   核心思想是思考推導公式，并以合适的方法实现（傻递归不可取）。

4. 三数之和（https://leetcode-cn.com/problems/3sum/submissions/）
   注意去重的技巧和双指针法运用：

    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """

        if len(nums) < 3:
            return []

        ret = []
        nums = sorted(nums)
        print nums
        for i in range(len(nums) - 2):
            if nums[i] > 0:
                continue
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            l, r = i + 1, len(nums) - 1
            while l < r:
                if nums[l] + nums[r] + nums[i] == 0:
                    ret.append([nums[i], nums[l], nums[r]])
                    l += 1
                    r -= 1
                    continue
                if nums[l] + nums[r] + nums[i] > 0:
                    r -= 1
                else:
                    l += 1
        return ret