leetcode 5.11-5.17

2020-05-14

136 只出现一次的数字
560 和为k的子数组

136. 只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/single-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

特点：相同数字的异或结果为0，数字与0的异或结果为自己本身。因此数组从头到尾异或一遍即可。

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ret = 0
        for num in nums:
            ret ^= num
        return ret

560. 和为k的子数组

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

示例 1 :

输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :

数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subarray-sum-equals-k
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一开始想的是先从头到尾遍历数组，每个位置更新为$nums[0]$到$nums[i]$的$sum$，然后从头到尾遍历$sum$数组，找到$sum[i] - sum[j] = k$的$i$ & $j$，但是由于数组中的元素不是正整数，不能通过简单对比$sum[i]$和$k$的大小来移动$i$ &$ j$，失败。

转换思路，从找$sum[i] - sum[j] = k$转变成找$sum[i] - k$。

用一个字典保存和为$sum$的、从$index=0$开始的连续子数组的个数；从头到尾遍历数组，计算$nums[0]$到$nums[i]$的和$sum$，如果$sum$在字典中，$dic[sum]++$，否则$dic[sum]=1$；$dic[sum-k]$表示0到$i$和为$sum-k$的子数组个数（也是 $i$ 的个数），假设当前数组下标为$j$，那么$i$到$j$是满足条件的连续子数组，$result += dic[sum - k]$。需要注意的是，当前结果只统计了从$index=1$开始的连续子数组个数，所以结果需要再加上$dic[k]$（从0开始和为k的连续子数组）；另外还需注意$k=0$的情况，在上述统计中，$sum[i] - sum[i] = 0$会被包括其中，因此最后要减掉$len(nums)$。

AC代码：

class Solution(object):
    def subarraySum(self, nums, k):
        dic = {}
        Sum = 0
        count = 0
        for num in nums:
            Sum += num
            if Sum in dic:
                dic[Sum] += 1
            else:
                dic[Sum] = 1

            if (Sum - k) in dic:
                count += dic[Sum-k]
        if k in dic:
            count += dic[k]
        if k == 0:
            count -= len(nums)
        return count

执行用时打败了100%的用户！！！第一次！！！开心。