LeetCode56. 合并区间

给出一个区间的集合，请合并所有重叠的区间。
奇技淫巧

首先取出每个区间的左边和右边，并对其排序
如果l[i+1]>r[i],说明第l_(i+1)个区间一定在前面i个区间的右边，并且中间有gap，不连续，就将前一次不连续的位置开始到i记录到结果中
j记录当前不连续区间的开始位置

# Definition for an interval.
# class Interval:
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution:
    def merge(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: List[Interval]
        """
        l,r = [],[]
        for i in intervals:
            l.append(i.start)
            r.append(i.end)
        l,r = sorted(l),sorted(r)
        j = 0
        res = []
        for i in range(len(intervals)):
            if i == len(intervals)-1 or l[i+1] > r[i]:
                res.append([l[j],r[i]])
                j = i+1
                
        return res

LeetCode57. 插入区间

给出一个无重叠的，按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
细节实现

比较list中每个区间的头，先找到第一个比newInterval.start大的位置，所以需要在这个前面插入，然后判断在这个位置插入的时候是否有区间可以与其合并，若可以合并，就合并成为新的newInterval，并且在list中删去与其合并的区间，直到不能合并位置，然后插入。

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution(object):
    def insert(self, intervals, newInterval):
        """
        :type intervals: List[Interval]
        :type newInterval: Interval
        :rtype: List[Interval]
        """
        n = len(intervals)
        if n==0:return [newInterval]
        i = 0
        while i<n:
            if intervals[i].start>=newInterval.start:
                break
            i += 1
        l = i-1
        while intervals and ((l>=0 and intervals[l].end>=newInterval.start) or (l<n-1 and intervals[l+1].start<=newInterval.end)):
            if l>=0 and intervals[l].end>=newInterval.start:
                newInterval.start = min(intervals[l].start,newInterval.start)
                newInterval.end = max(intervals[l].end,newInterval.end)
                intervals.pop(l)
                l -= 1
                n -= 1
                continue
            if l<n-1 and intervals[l+1].start<=newInterval.end:
                newInterval.end = max(intervals[l+1].end,newInterval.end)
                newInterval.start = min(intervals[l+1].start,newInterval.start)
                intervals.pop(l+1)
                n -= 1
                continue
        intervals.insert(l+1,newInterval)
        return intervals

LeetCode 128 最长连续序列

给定一个未排序的整数数组，找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。

哈希表

class Solution(object):
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        hash_table = set()
        for i in nums:
            hash_table.add(i)
        max_len = 0
        for i in nums:
            length = 1
            j = i+1
            while j in hash_table:
                hash_table.remove(j)
                j += 1
                length += 1
                
            j = i-1
            while j in hash_table:
                hash_table.remove(j)
                j -= 1
                length += 1
            max_len = length if length > max_len else max_len
        return max_len

LeetCode560. 和为K的子数组

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
哈希表

用一个哈希表记录从0开始到当前位置数组的累加和sum(nums[0:i])的值出现的次数，若在第i个位置的和为sum_，那么sum_-k曾经出现过的话，出现的位置j到i的连续子数组的和肯定为k

class Solution(object):
    def subarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        
        n = len(nums)
        d = {0:1}
        sum_,count_ = 0,0
        for i in range(n):
            sum_ += nums[i]
            if sum_ - k in d:
                count_ += d[sum_ - k]
            if sum_ in d:
                d[sum_] += 1
            else:
                d[sum_] = 1
        return count_