Day 9 | 7/9

[tech-cow]

今日任务 (Two Pointers)

• 看资源
• 总结

刷题任务

Leetcode

• 28 Implement strStr()
• 15 3Sum
• 16 3Sum Closest

Lintcode

• 31. Partition Array
• 587. Two Sum - Unique pairs
• 533. Two Sum - Closest to target
• 443. Two Sum - Greater than target

[tech-cow]

Leetcode

28 Implement strStr()

类型：滑动窗口
Time Complexity O(n)
Space Complexity O(1)

设置区间，从左往右边滑动

class Solution(object):
    def strStr(self, s, target):
        if not target: return 0
        l, r = 0 , len(target)
        while r <= len(s):
            if s[l:r] == target:
                return l
            else:
                l += 1
                r += 1
        return -1

15 3Sum

类型：固定区间斗鸡眼
Time Complexity O(n^2)
Space Complexity O(1)

大概思路是外围For一遍数组，然后在每次迭代的时候，设置[l,r]的区间，区间范围为l , r = i + 1, len(nums) - 1, 这样比对的数就有3个，分别是nums[i], nums[l] 和 nums[r].
最终要达到的效果是: nums[l] + nums[r] == -nums[i]
这道题一定要记住去重，不仅仅是区间的l和r要去重，外围的i也需要去重。去重的方法如下:
i去重： if i == 0 or nums[i] > nums[i-1]:
l去重： while l < r and nums[l] == nums[l-1]: l += 1
r去重： while l < r and nums[r] == nums[r+1]: r -= 1

class Solution(object):
    def threeSum(self, nums):
        res = []
        nums.sort()
        if len(nums) < 3:
            return res

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

16 3Sum Closest

类型：固定区间斗鸡眼
Time Complexity O(n^2)
Space Complexity O(1)

大概框架3Sum思路一样，唯一不需要的就是太考虑去重问题。

class Solution(object):
    def threeSumClosest(self, nums, target):
        nums.sort()
        res = nums[0] + nums[1] + nums[2]
        
        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i-1]: continue
            l , r = i + 1, len(nums) - 1
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if s == target:
                    return s
                if abs(s - target) < abs(res - target):
                    res = s
                if s < target:
                    l += 1
                elif s > target:
                    r -= 1
        return res

[tech-cow]

Lintcode

31. Partition Array

类型：斗鸡眼
Time Complexity O(n)
Space Complexity O(1)

斗鸡眼，左右指针Value根据大小换位。

class Solution:
    def partitionArray(self, nums, k):
        l, r = 0, len(nums)-1
        while l < r:
            while l < r and nums[l] < k:
                l += 1
            while l < r and nums[r] >= k:
                r -= 1
            if l < r:
                nums[l], nums[r] = nums[r], nums[l]
        for i, num in enumerate(nums):
            if num >= k:
                return i
        return len(nums)

587. Two Sum - Unique pairs

类型：斗鸡眼(去重)
Time Complexity O(nlogn)
Space Complexity O(1)

主要记得去重，其他没什么。

class Solution:
    def twoSum6(self, nums, target):
        nums.sort()
        cnt, l, r, = 0, 0, len(nums) - 1
        while l < r:
            if nums[l] + nums[r] == target:
                cnt += 1
                l += 1; r -= 1
                while l < r and nums[l] == nums[l-1]: l += 1
                while l < r and nums[r] == nums[r+1]: r -= 1
            elif nums[l] + nums[r] < target:
                l += 1
            else:
                r -= 1
        return cnt

587. Two Sum - Unique pairs

类型：斗鸡眼
Time Complexity O(nlogn)
Space Complexity O(1)

3Sum Closest的简单版本。

class Solution:
    def twoSumClosest(self, nums, target):
        nums.sort()
        if len(nums) < 2:
            return -1
        diff = abs(target - (nums[0] + nums[1]))
        
        l , r = 0 , len(nums) - 1
        while l < r:
            s = (nums[l] + nums[r])
            if target - s == 0:
                return 0
            if abs(target - s) < diff:
                diff = abs(target - s)
            if s > target:  
                r -= 1
            else:
                l += 1
        return diff

443. Two Sum - Greater than target

类型：斗鸡眼
Time Complexity O(nlogn)
Space Complexity O(1)

需要做的是把所有的pair相加并返回，举例如下
如果排序好的数组为[1, 2,3,4,7,9]。target是5。
如果l和r是：l, r = 0, len(nums) - 1, l + r也就是9 + 1就已经大于5，说明r - l的所有数都大于5，那我们找到了和所有9相加大于5的，可以最大值缩进了r -= 1
同理，当Sum比Target小的时候，我们最小值缩进，l += 1即可

class Solution:
    def twoSum2(self, nums, target):
        nums.sort()
        res = 0
        if len(nums) < 2:
            return 0
        l, r = 0, len(nums) - 1
        while l < r:
            s = nums[l] + nums[r]
            if s > target:
                res += r - l
                r -= 1
            else:
                l += 1
        return res