01.数组

# 01.求两数之和

题目

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1]

1
2
3
4
5
6

# 1.1 python答案

nums = [2,11,15,3,6,7]
target = 9
def towSum(nums, target):
    dic = {}
    for k, v in enumerate(nums):
        if target - v in dic:  # 证明字典中存在一个value与当前value和等于target
            print(dic[target - v], k)  # 打印这两个值的索引
        dic[v] = k
towSum(nums, target)
# 3 4
# 0 5

1
2
3
4
5
6
7
8
9
10
11

# 1.2 golang答案

package main

import "fmt"

func twoSum(nums []int, target int) []int {
	tmpMap := map[int]int{}
	for index, num := range nums {
		_,ok := tmpMap[target-num]
		if ok {  // 证明字典中存在一个value与当前value和等于target
			return []int{tmpMap[target-num], index}  // 返回这两个值的索引
		}
		tmpMap[num] = index
	}
	return []int{}
}

func main()  {
	nums := []int{2,7,11,15}
	target := 9
	li := twoSum(nums, target)
	fmt.Println(li)  // [0,1]
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 02.最大子序和

# 2.1 题目描述

最大子序和 (opens new window)
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

1
2
3

# 2.2 python

基本思路就是遍历一遍，用两个变量，一个记录最大的和，一个记录当前的和。
如果当前和小于0，当前最长序列到此为止。以该元素为起点继续找最大子序列
时空复杂度貌似还不错......（时间复杂度 O(n)，空间复杂度 O(l)

def maxSub(nums):
	max_ = nums[0]  # 假设第一个为最大和
	for i in range(1, len(nums)):
		if nums[i - 1] > 0:  # 如果当前和大于0就将当前和加上当新数据，否则重新开始当前和
			nums[i] += nums[i - 1]
		max_ = max(max_, nums[i])  # 当前和 于 记录最大和比较，大的为新的最大和
	return max_

nums = [-2,1,-3,4,-1,2,1,-5,4]
print(maxSub(nums))  #  6 ==》[4,-1,2,1]

1
2
3
4
5
6
7
8
9
10

# 2.3 golang

基本思路就是遍历一遍，一个记录最大的和，一个记录当前的和。
如果当前的和大于0，就继续加下一个元素，然后比较max，如果更大就更新max
时空复杂度貌似还不错......（时间复杂度 O(n)，空间复杂度 O(l)

package main

import "fmt"

func maxSubArray(nums []int) int {
	max := nums[0]  // 假设第一个为最大和
	for i := 1; i < len(nums); i++ {
		if nums[i] + nums[i-1] > nums[i] {   // 如果nums[i-1]当前和大于0，将当前和加上当新数据，否则重新开始当前和
			nums[i] += nums[i-1]
		}
		if nums[i] > max {  // 当前和与记录最大的和比较，如果当前和更大就更新
			max = nums[i]
		}
	}
	return max
}

func main() {
	nums := []int{-2,1,-3,4,-1,2,1,-5,4}
	fmt.Println( maxSubArray(nums) )  // 6
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 03.买卖股票的最佳时机

买卖股票的最佳时机 (opens new window)

# 3.1 题目要求

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。

输入: [7,4,6,3,1]
输出: 2

1
2

# 3.2 python

有 买入（buy） 和 卖出（sell） 这两种状态
当天买的话意味着损失 -prices[i]，当天卖的话意味着增加 prices[i]，当天卖出总的收益就是 buy+prices[i]
所以我们只要考虑当天买和之前买哪个收益更高，当天卖和之前卖哪个收益更高。
- buy = max(buy, -price[i]) （注意：根据定义 buy 是负数）
- sell = max(sell, prices[i] + buy)

s = [7,4,6,3,1]

def maxProfit(prices):
    if len(prices) <= 1:
        return 0
    buy = prices[0]  # 当天买的话意味着损失 -prices[i]
    sell = 0
    for i in prices:
        buy = min(buy, i)  # 当前买的价格 比 以前买入的大,就在当前节点买入
        sell = max(sell, i-buy)  # 卖的价钱 = 现在成交价格i - 购买价格buy
    return sell

print(maxProfit(s))    # 2

1
2
3
4
5
6
7
8
9
10
11
12
13

# 3.3 golang

package main

import (
	"fmt"
)

func maxProfit(prices []int) int {
	if len(prices) <= 1{
		return 0
	}
	buy := prices[0]  // 当天买的话意味着损失 -prices[i]
	sell := 0       // 初始化利润为0
	for _, price := range prices{
		if price < buy {  // 当前买的价格 比 以前买入的大,就在当前节点买入
			buy = price   // 卖的价钱 = 现在成交价格i - 购买价格buy
		}
		if price-buy > sell{  // 如果当前价格减卖的价格 大于记录的最大利润，就更新最大利润
			sell = price-buy
		}
	}
	return sell
}

func main() {
	prices := []int{7,4,6,3,1}
	ret := maxProfit(prices)
	fmt.Println(ret)  // 2
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

# 04.买卖股票最大亏损

# 4.1 题目要求

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大亏损。
注意你不能在买入股票前卖出股票。

输入: [7,6,4,3,1]
输出: -6

1
2

# 4.2 python

s = [7,6,4,3,1]

class Solution:
    def maxProfit(self, prices):
        if len(prices)<=1: 
            return 0
        buy = -prices[0]  # 当天买的话意味着损失 -prices[i]
        sell=0         # 初始化利润为0
        for i in prices:
            buy = min(buy, -i)  # 当前价格与买进价格那个大就为新的买进价格
            sell= min(sell, i + buy)  # 计算最大亏损
        return sell

print( Solution().maxProfit(s) )

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 05.合并两个有序数组

# 5.1 题目说明

合并两个有序数组 (opens new window)
给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中*，*使 nums1 成为一个有序数组。
初始化 nums1 和 nums2 的元素数量分别为 m 和 n
你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]

1
2

# 5.2 普通合并方案

def merge(num1, num2):
	tmp = []
	n1 , n2 =0, 0  # 使用n1, n2两个指针分别指向num1, num2两个数组开始位置
	while n1 < len(num1) and n2 < len(num2):  # 只要有一个指针遍历完就结束
		if num1[n1] < num2[n2]:
			tmp.append(num1[n1])
			n1 = n1 + 1
		else:
			tmp.append(num2[n2])
			n2 = n2 + 1
	return tmp + num1[n1:] if n1 < len(num1) else tmp + num2[n2:]  # 将没有遍历完的数组的数据局追加

num1 = [1,4,7,15,19]
num2 = [2,4,9]
print( merge(num1, num2) )  # [1, 2, 4, 4, 7, 9, 15, 19]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 5.3 python双指针

将两个数组看作队列，每次从两个数组头部取出比较小的数字放到结果中。
我们为两个数组分别设置一个指针p1 与 p2 来作为队列的头部指针

def merge(nums1, m, nums2, n):
    tmp = []
    p1, p2 = 0, 0  # 分别设置一个指针p1 与 p2 来作为队列的头部指针
    while p1 < m or p2 < n:
        if p1 == m:  # p1 == m证明 nums1遍历完了，直接遍历num2，添加到tmp中即可
            tmp.append(nums2[p2])
            p2 += 1
        elif p2 == n:  # p2 == n证明 nums2遍历完了，直接遍历num1，添加到tmp中即可
            tmp.append(nums1[p1])
            p1 += 1
        elif nums1[p1] < nums2[p2]:
            tmp.append(nums1[p1])
            p1 += 1
        else:
            tmp.append(nums2[p2])
            p2 += 1
    nums1[:] = tmp  # [1, 2, 2, 3, 5, 6]
    print(nums1)

nums1 = [1,2,3,0,0,0]  # nums1 的空间大小等于 m + n
m = 3                  # nums1的元素数量为m个
nums2 = [2,5,6]
n = 3                  # nums2的元素数量为n个
merge(nums1,m, nums2, n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 5.4 golang双指针

package main

import "fmt"

func merge(nums1 []int, m int, nums2 []int, n int) {
	//nums1 = nums1[:m]
	tmp := []int{}
	p1, p2 := 0, 0  // 分别设置一个指针p1 与 p2 来作为队列的头部指针
	for p1 < m || p2 < n {
		if p1 == m {  // p1 == m证明 nums1遍历完了，直接遍历num2，添加到tmp中即可
			tmp = append(tmp, nums2[p2:]...)
			p2 += 1
		}else if p2 == n {  // p2 == n证明 nums2遍历完了，直接遍历num1，添加到tmp中即可
			tmp = append(tmp, nums1[p1:]...)
			p1 += 1
		}else if nums1[p1] < nums2[p2] {
			tmp = append(tmp, nums1[p1])
			p1 += 1
		}else {
			tmp = append(tmp, nums2[p2])
			p2 += 1
		}
	}
	copy(nums1, tmp)
}

func main() {
	nums1 := []int{1,2,3,0,0,0}  // nums1 的空间大小等于 m + n
	nums2 := []int{2,5,6}
	m,n := 3,3
	merge(nums1, m, nums2, n)
	fmt.Println(nums1) // [1 2 2 3 5 6]
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

# 06.数组中重复的数字

数组中重复的数字 (opens new window)

# 6.1 题目描述

找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。
数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。
请找出数组中任意一个重复的数字。

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

1
2
3

# 6.2 python

利用字典查找时间复杂度为O(1)的特点

def findRepeat(nums):
    d = {}
    for i in nums:
        if i in d:
            return i
        d[i] = True

nums = [2, 3, 1, 0, 2, 5, 3]
print( findRepeat(nums) )  # 2

1
2
3
4
5
6
7
8
9

# 6.2 golang

package main

import "fmt"

func findRepeatNumber(nums []int) int {
	d := map[int]bool{}
	for _,v := range nums {
		_,ok := d[v]
		if ok{
			return v
		}
		d[v] = true
	}
	return 0
}

func main() {
	nums := []int{2, 3, 1, 0, 2, 5, 3}
	v := findRepeatNumber(nums)
	fmt.Println(v)  // 2
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 07.删除有序数组中重复项

删除有序数组中的重复项 (opens new window)

# 7.1 题目描述

给你一个有序数组 nums ，请你** 原地 (opens new window)** 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 (opens new window)修改输入数组 并在使用 O(1) 额外空间的条件下完成。

输入：nums = [1,1,2]
输出：2, nums = [1,2]

1
2

# 7.2 python

使用 count指针记录当前列表中无重复数字的长度
使用 i 指针遍历列表，如果相邻两个元素不相等，什么都不处理
如果相邻两个元素不相等，就将不重复的值放到 count指针位置
遍历完结果：

   nums = [0, 0, 1, 1, 1, 2, 2 ,3, 3, 4]   # 原始列表
   nums = [0, 1, 2, 3, 4, 2, 2, 3, 3, 4]   # 遍历后结果，count=5，遍历后取出 nums[5]，就是目标结果

1
2

def removeDulp(nums):
    count = 1
    for i in range(1, len(nums)):
        if nums[i] != nums[i - 1]:
            nums[count] = nums[i]  # 如果相邻两个元素不相等，就将 不重复的值放到 count指针位置
            count += 1
    return count, nums

nums = [0,0,1,1,1,2,2,3,3,4]
print( removeDulp(nums) )  # (5, [0, 1, 2, 3, 4, 2, 2, 3, 3, 4])

1
2
3
4
5
6
7
8
9
10

# 7.3 golang

package main

import "fmt"

func removeDuplicates(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	count := 1
	for i := 1; i < len(nums); i++ {
		if nums[i] != nums[i - 1] {
			nums[count] = nums[i]  //  如果相邻两个元素不相等，就将 不重复的值放到 count指针位置
			count += 1
		}
	}
	return count
}

func main() {
	nums := []int{1,1,2}
	v := removeDuplicates(nums)
	fmt.Println(v)  // 2
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 08.两数之和 II

两数之和 II - 输入有序数组 (opens new window)

# 8.1 题目描述

给定一个已按照 升序排列 的整数数组 numbers
请你从数组中找出两个数满足相加之和等于目标数 target
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素

输入：numbers = [2,3,4], target = 6
输出：[1,3]
输入：numbers = [-1,0], target = -1
输出：[1,2]

1
2
3
4

# 8.2 python

初始时两个指针分别指向第一个元素位置和最后一个元素的位置。
每次计算两个指针指向的两个元素之和，并和目标值比较。
如果两个元素之和等于目标值，则发现了唯一解。
如果两个元素之和小于目标值，则将左侧指针右移一位。
如果两个元素之和大于目标值，则将右侧指针左移一位

def twoSum(numbers, target):
    low, high = 0, len(numbers) - 1  # 初始时两个指针分别指向第一个元素位置和最后一个元素的位置。
    while low < high:  # 只要左右指针没有相遇就循环
        total = numbers[low] + numbers[high]
        if total == target:   # 判断两个元素之和等于目标值，则发现了唯一解
            return [low + 1, high + 1]
        elif total < target:
            low += 1
        else:
            high -= 1
    return [-1, -1]

if __name__ == '__main__':
    numbers = [2,3,4]
    target = 6
    print( twoSum(numbers, target) )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 8.3 golang

package main

import "fmt"

func twoSum(numbers []int, target int) []int {
	low, high := 0, len(numbers) - 1  // 初始时两个指针分别指向第一个元素位置和最后一个元素的位置。
	for low < high {  // 只要左右指针没有相遇就循环
		total := numbers[low] + numbers[high]
		if total == target{  // 判断两个元素之和等于目标值，则发现了唯一解
			return []int{low+1, high+1}
		}else if total < target {
			low += 1
		}else {
			high -= 1
		}
	}
	return nil
}

func main() {
	nums := []int{2,7,11,15}
	target := 9
	v := twoSum(nums, target)
	fmt.Println(v)  // [1 2]
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# 09.多数元素

# 9.1 题目描述

给定一个大小为 n 的数组，找到其中的多数元素。
多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素

输入：[3,2,3]
输出：3
输入：[2,2,1,1,1,2,2]
输出：2

1
2
3
4

# 9.2 解题思路

我们先将 nums 数组排序，然后返回上文所说的下标对应的元素。
应为肯定出现多数元素，那么排序后，中位数一定是这个多数

def manyNums(nums):
    nums.sort()
    return nums[len(nums) // 2]

nums = [3,2,3]
print( manyNums(nums) )  # 3

1
2
3
4
5
6

# 10.旋转数组的最小数字

旋转数组的最小数字 (opens new window)

# 10.1 题目描述

把一个有序数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

输入：[3,4,5,1,2]
输出：1
# 上面旋转数组的最小值就为1

1
2
3

# 10.2 python

左边界为low，右边界为high，区间的中点为 m,被分为下面三情况
- 如果 m的值小于 R的值，最小值一定在左半部分
- 如果m的值大于R的值，最小值一定在右半部分
- 如果中间值m等于 R的值，那么右指针就向左移动一位

def minArray(nums):
    # 左边界为L，右边界为R，区间的中点为 m
    L, R = 0, len(nums) - 1
    while L < R:
        m = L + (R - L) // 2
        if nums[m] < nums[R]:    # 如果 m的值小于 R的值，最小值一定在左半部分
            R = m
        elif nums[m] > nums[R]:  # 如果m的值大于R的值，最小值一定在右半部分
            L = m + 1
        else:                    # 如果中间值m等于 R的值，那么右指针就向左移动一位
            R -= 1               # R右指针向左移动，值是会变小的
    return nums[L]

nums = [3,4,5,1,2]
print( minArray( nums ) )  # 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 10.3 golang

package main

import "fmt"

func minArray(numbers []int) int {
  // 左边界为L，右边界为R，区间的中点为 m
	L, R := 0, len(numbers) - 1
	for L < R {
		m := L + (R-L) / 2
		if numbers[m] < numbers[R] {  // 如果 m的值小于 R的值，最小值一定在左半部分
			R = m
		} else if numbers[m] > numbers[R] {  // 如果m的值大于R的值，最小值一定在右半部分
			L = m + 1
		} else {  // 如果中间值m等于 R的值，那么右指针就向左移动一位
			R -= 1  // R右指针向左移动，值是会变小的
		}
	}
	return numbers[L]
}

func main() {
	nums := []int{3,4,5,1,2}
	v := minArray(nums)
	fmt.Println(v)  // 1
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# 11.两个数组的交集

两个数组的交集 (opens new window)

# 11.1 题目描述

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]

1
2

# 11.2 python

def disNum(nums1, nums2):
    _set = set(nums1)  # 将nums1转换成集合
    result = []

    for num in nums2:
        if num in _set:    # 如果nums2中元素在集合中
            result.append(num)
            _set.discard(num)   # 集合中去除刚刚已经添加的元素，避免重复解
    return result

if __name__ == '__main__':
    nums1 = [4,9,5]
    nums2 = [9,4,9,8,4]
    print( disNum(nums1, nums2) )

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 11.3 golang

package main

import "fmt"

func intersection(nums1 []int, nums2 []int) []int {
	set1 := map[int]bool{}
	for _, v := range nums1 {  // 将nums1转换成集合
		set1[v] = true
	}
	tmp := []int{}
	for _,v2 := range nums2 {
		_,ok := set1[v2]
		if ok {           // 如果nums2中元素在集合中
			tmp = append(tmp,v2)
			delete(set1, v2)  // 集合中去除刚刚已经添加的元素，避免重复解
		}
	}
	return tmp
}

func main() {
	nums1 := []int{4,9,5}
	nums2 := []int{9,4,9,8,4}
	v := intersection(nums1, nums2)
	fmt.Println(v)  // [9 4]
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# 12.加一

# 12.1 题目描述

加一 (opens new window)
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

输入：digits = [1,2,3]
输出：[1,2,4]
输入：digits = [9,9,9]
输出：[1,0,0,0]

1
2
3
4

# 12.2 python

def plusOne(li):
	tmp = 1             # 设置临时变量 1
	n = len(li) - 1     # 列表最右侧元素下标为 n
	while (n >= 0):     # 从列表右侧向左遍历
		sum = li[n] + tmp   # 当前值加上井位为当前位置 总值
		digit = sum % 10    # 取余获得当前位置值
		li[n] = digit
		tmp = sum // 10     # 井位
		n -= 1              # 下标向左移动一位

	if (tmp > 0):           # 如果是 999这种情况，循环结束列表还存在井位
		li = [tmp] + li     # 直接将井位添加到列表头部即可
	return li

print(plusOne([9,9,9]))   # [1, 0, 0, 0]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 12.3 golang

package main

import "fmt"

func plusOne(digits []int) []int {
	tmp := 1              // 设置临时变量 1
	n := len(digits) - 1  // 列表最右侧元素下标为 n
	for n >= 0 {          // 从列表右侧向左遍历
		sum := digits[n] + tmp  // 当前值加上井位为当前位置 总值
		digit := sum % 10       // 取余获得当前位置值
		digits[n] = digit
		tmp = sum / 10       // 井位
		n -= 1               // 下标向左移动一位
	}
	if tmp > 0 {           // 如果是 999这种情况，循环结束列表还存在井位
		digits = append([]int{tmp}, digits...)  // 直接将井位添加到列表头部即可
	}
	return digits
}

func main() {
	nums := []int{9,9,9}
	v := plusOne(nums)
	fmt.Println(v)  // [1 0 0 0]
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# 13.和为s的连续正数序列

# 13.1 题目描述

和为s的连续正数序列 (opens new window)
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

输入：target = 9
输出：[[2,3,4],[4,5]]
输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]

1
2
3
4

# 13.2 python滑动窗口

参考 (opens new window)
我们一开始要找的是 1 开头的序列，只要窗口的和小于 target，窗口的右边界会一直向右移动。
假设 1+2+⋯+8 小于 target，再加上一个 9 之后，发现1+2+⋯+8+9 又大于 target 了。
这说明 1 开头的序列找不到解。此时滑动窗口的最右元素是 9。
接下来，我们需要找 2 开头的序列，我们发现，2+⋯+8 < 1+2+⋯+8 <target。
这说明 2 开头的序列至少要加到 9。
那么，我们只需要把原先 1~9 的滑动窗口的左边界向右移动，变成 2~9 的滑动窗口，然后继续寻找。
而右边界完全不需要向左移动。
以此类推，滑动窗口的左右边界都不需要向左移动，所以这道题用滑动窗口一定可以得到所有的解。
时间复杂度是 O(n)。

def findTarget(target):
    i = 1    # 滑动窗口的左边界
    j = 1    # 滑动窗口的右边界
    sum = 0   # 滑动窗口中数字的和
    res = []

    while i <= target // 2:
        if sum < target:   # 右边界向右移动
            sum += j
            j += 1
        elif sum > target:
            sum -= i      # 左边界向右移动
            i += 1
        else:
            arr = list(range(i, j))   # 记录结果
            res.append(arr)
            sum -= i     # 左边界向右移动
            i += 1
    return res

print( findTarget(9) )  # [[2, 3, 4], [4, 5]]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 13.3 golang滑动窗口

package main

import "fmt"

func findContinuousSequence(target int) [][]int {
	i := 1     // 滑动窗口的左边界
	j := 1     // 滑动窗口的右边界
	sum := 0   // 滑动窗口中数字的和
	res := [][]int{}  // 初始化这样的数据结构 [[2, 3, 4], [4, 5]]
	for i <= target / 2 {
		if sum < target {
			sum += j           // 右边界向右移动
			j += 1
		}else if sum > target {
			sum -= i           // 左边界向右移动
			i += 1
		}else {
			arr := []int{}
			for i1 := i; i1 < j; i1++ {
				arr = append(arr, i1)
			}
			res = append(res, arr)  // 记录结果
			sum -= i                // 左边界向右移动
			i += 1
		}
	}
	return res
}

func main() {
	target := 9
	v := findContinuousSequence(target)
	fmt.Println(v)  // [[2 3 4] [4 5]]
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

# 14.两个数组的交集 II

# 14.1 题目描述

# 两个数组的交集 II (opens new window)
给定两个数组，编写一个函数来计算它们的交集。

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

1
2
3
4

# 14.2 python字典方法

def findCom(nums1, nums2):
	d = {}
	for i in nums1:
		d[i] = d.get(i,0) + 1

	tmp = []
	for i in nums2:
		if i in d:
			tmp.append(i)
			d[i] = d.get(i) - 1
			if d[i] == 0: d.pop(i)
	return tmp

nums1 = [4, 9, 4, 5]
nums2 = [9, 4, 9, 8, 4]
print(findCom(nums1, nums2))  # [4, 9]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 14.3 python排序双指针

将两个数组进行排序，随后用双指针顺序查找相同的元素
创建一个指针 i指向 nums1 数组首位，指针 j 指向 nums2 数组首位。
创建一个临时栈，用于存放结果集。
开始比较指针 i 和指针 j的值大小，若两个值不等，则数字小的指针，往右移一位。
若指针 i和指针 j的值相等，则将交集压入栈。
若 nums 或 nums2 有一方遍历结束，代表另一方的剩余值，都是唯一存在，且不会与之产生交集的。

def findCom(nums1, nums2):
	nums1.sort()
	nums2.sort()
	ret = []  # 创建一个临时栈，用于存放结果集
	i, j = 0, 0
	while i < len(nums1) and j < len(nums2):
		# 若两个值不等，则数字小的指针，往右移一位。
		if nums1[i] < nums2[j]:
			i += 1
		elif nums1[i] == nums2[j]:  # 如果两个值相等，将数据添加，两个指针都向右移动一位
			ret.append(nums1[i])
			i += 1
			j += 1
		else:
			j += 1
	return ret


nums1 = [4, 9, 5]
nums2 = [9, 4, 9, 8, 4]
print(findCom(nums1, nums2))  # [4, 9]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 14.4 golang排序双指针

package main

import (
	"fmt"
	"sort"
)

func intersect(nums1 []int, nums2 []int) []int {
	sort.Ints(nums1)
	sort.Ints(nums2)
	ret := []int{}  // 创建一个临时栈，用于存放结果集
	i,j := 0,0    // i,j两个指针分别指向nums1,nums2的头部
	for i < len(nums1) && j < len(nums2) {  // 只要有一个数组遍历完就结束循环
		if nums1[i] < nums2[j] {  // 若两个值不等，则数字小的指针，往右移一位。
			i += 1
		}else if nums1[i] == nums2[j] {
			ret = append(ret, nums1[i])
			i += 1
			j += 1
		}else {
			j += 1
		}
	}
	return ret
}

func main() {
	num1 := []int{1,2,2,1}
	num2 := []int{2,2}
	v := intersect(num1, num2)
	fmt.Println(v)  // [2,2]
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

# 15.找到所有数组中消失的数字

找到所有数组中消失的数字 (opens new window)

# 15.1 题目描述

给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的整型数组，数组中的元素一些出现了两次，另一些只出现一次。
找到所有在 [1, n] 范围之间没有出现在数组中的数字。
您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。

输入:
[4,3,2,7,8,2,3,1]
输出:
[5,6]

1
2
3
4

# 15.2 python

由于nums的数字范围均在 [1,n]中，我们可以利用这一范围之外的数字，来表达「是否存在」的含义。
遍历 nums，每遇到一个数 x，就让 nums[x−1] 增加 n
由于nums 中所有数均在 [1,n]中，增加以后，这些数必然大于 n
最后我们遍历nums，若]nums[i] 未大于 n，就说明没有遇到过数i+1,这样我们就找到了缺失的数字。

def findNums(nums):
    n = len(nums)
    for num in nums:
        x = (num - 1) % n   # 由于原始值都小于n，所以对n取余可以找到原始的这个数
        nums[x] += n   # 遍历 nums，每遇到一个数 x，就让 nums[x−1] 增加 n
    # 最后我们遍历nums，若]nums[i] 未大于 n，就说明没有遇到过数i+1,这样我们就找到了缺失的数字
    ret = [i + 1 for i, num in enumerate(nums) if num <= n]
    return ret

nums = [4,3,2,7,8,2,3,1]
print( findNums(nums) )  # [5, 6]

1
2
3
4
5
6
7
8
9
10
11

# 16.列表去重

# 16.1 python

#1、set去重
a=[1,2,3,4,1,2,3,4]
print( list(set(a)) )    # [1, 2, 3, 4]

#2、使用字典去重
b = {}
b=b.fromkeys(a).keys()
print(list(b))                #  [1, 2, 3, 4]

1
2
3
4
5
6
7
8

列表去重：不改变顺序

a=[1,2,3,4,1,2,3,4]

#1、去重不改变顺序
d = {}
tmp = []
for i in a:
    if not d.get(i):
        tmp.append(i)
        d[i] = True
print(tmp)             #  [1, 2, 3, 4]

1
2
3
4
5
6
7
8
9
10

# 16.2 golang

package main

import (
	"fmt"
)

func listRemoveDupl(nums []int) []int {
	d := map[int]bool{}
	tmp := []int{}
	for _,v := range nums {
		_,ok := d[v]
		if !ok {  // 如果没有在字典中就添加到列表中，同时记录到字典中
			tmp = append(tmp, v)
			d[v] = true
		}
	}
	return tmp
}

func main() {
	nums := []int{1,2,2,3,5,4,6,3,1}
	v := listRemoveDupl(nums)
	fmt.Println(v)  // [1 2 3 5 4 6]
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 17.实现enumerate函数

l = [1,2,3,4]
def my_enumerate(l):
    n = 0
    for val in l:
        print(n,val)
        n += 1
my_enumerate(l)

1
2
3
4
5
6
7

# 18.列表连续相同数据放一起

# 18.1 题目要求

将列表：# [1,2,2,3,4,4,5,6,6,6,7,8,2,2,2]
转换成：# [[1], [2, 2], [3], [4, 4], [5], [6, 6, 6], [7], [8], [2, 2, 2]]

1
2

# 18.2 解题思路

# -*- coding: utf-8 -*-
li = [1,2,2,3,4,4,5,6,6,6,7,8,2,2,2]
def func(li):
   ret = []
   n = 1
   while n < len(li):
      if li[n] == li[n-1]:
         tmp = [li[n-1]]
         while n < len(li) and li[n] == li[n-1]:
            tmp.append(li[n])
            n = n + 1
         else:
            ret.append(tmp)
      else:
         ret.append([li[n-1]])
      n = n + 1
   return ret

print( func(li) )
# [[1], [2, 2], [3], [4, 4], [5], [6, 6, 6], [7], [8], [2, 2, 2]]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 19.盛最多水的容器

盛最多水的容器 (opens new window)

# 19.1 题目描述

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。
在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

示例 1：
输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：
输入：height = [1,1]
输出：1

1
2
3
4
5
6
7
8

# 19.2 python

算法流程：
- 设置双指针 i,j 分别位于容器壁两端，根据规则移动指针（后续说明）
- 并且更新面积最大值 res，直到 i == j 时返回 res
指针移动规则与证明：
- 每次选定围成水槽两板高度 h[i],h[j] 中的短板，向中间收窄 1格
- 由于水槽的实际高度由两板中的短板决定，则可得面积公式 S(i, j) = min(h[i], h[j]) × (j - i)
- 在每一个状态下，无论长板或短板收窄 1格，都会导致水槽 底边宽度 -1
- 左右长度，那个小，就移动哪一个，才有可能让面积增大

def maxArea(nums):
    # L左指针，J右指针, 面积S(i, j) = min(h[i], h[j]) × (j - i)
    L, R, S = 0, len(nums) - 1, 0
    while L < R:  # 只要左右指针不重合就一直循环
        if nums[L] < nums[R]:  # 如果做指针小，那么移动左指针才有可能使面积增大
            S = max(S, nums[L] * (R - L))
            L += 1
        else:  # 否则若果有指针小，只有移动右指针才有可能使面积增大
            S = max(S, nums[R] * (R - L))
            R -= 1
    return S

nums = [1,8,6,2,5,4,8,3,7]
print( maxArea(nums) )

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 19.3 golang

package main

import (
	"fmt"
)

func maxArea(height []int) int {
  // L左指针，J右指针, 面积S(i, j) = min(h[i], h[j]) × (j - i)
	L, R, S := 0, len(height)-1, 0
	for L < R {                         // 只要左右指针不重合就一直循环
		  if height[L] < height[R] {
			  if height[L] * (R - L) > S {  // 如果做指针小，那么移动左指针才有可能使面积增大
				  S = height[L] * (R - L)
			  }
			  L += 1
		  } else {         // 否则若果有指针小，只有移动右指针才有可能使面积增大 
			  if height[R] * (R - L) > S {
				  S = height[R] * (R - L)
			  }
			  R -= 1
		  }
	}
	return S
}

func main() {
	nums := []int{1,8,6,2,5,4,8,3,7}
	v := maxArea(nums)
	fmt.Println(v)  // 49
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# 20.合并区间

# 20.1 题目说明

合并区间 (opens new window)
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi]
请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]

1
2
3

# 20.2 解题思路

首先，我们将列表中的区间按照左端点升序排序
相邻两个列表如果前一个列表最大值小于下一个列表最小值，肯定无需合并，直接添加到空列表
否则找到这两个列表中的最大值，拓展区间

def merge(intervals):
    intervals.sort(key=lambda x: x[0])  # 首先，我们将列表中的区间按照左端点升序排序
    merged = []
    for interval in intervals:
        # 如果列表为空，或者 一个列表右边的值 < 下一个列表左边的元素
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)  # 直接添加，无需合并
        else:
            # 否则的话，我们就可以与上一区间进行合并, 右边值为两个列表右侧较大的值
            merged[-1][1] = max(merged[-1][1], interval[1])

    return merged

intervals = [[2,3],[1,6],[8,10],[15,18]]
print(merge(intervals))  # [[1, 6], [8, 10], [15, 18]]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 21.搜索旋转排序数组

# 21.1 题目描述

搜索旋转排序数组 (opens new window)
整数数组 nums 按升序排列，数组中的值 互不相同
nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的索引，否则返回 -1

原始数组：[0,1,2,4,5,6,7]  
旋 转 后：[4,5,6,7,0,1,2]
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

1
2
3
4

# 21.2 解题思路

可以发现的是，我们将数组从中间分开成左右两部分的时候，一定有一部分的数组是有序的

def search(nums, target):
    if not nums:
        return -1
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = (l + r) // 2
        if nums[mid] == target:
            return mid

        # 如果 第一个元素 < 中间值 证明前半部分有序
        if nums[0] <= nums[mid]:
            # 如果目标元素 在前半部分，就移动右指针为 mid-1
            if nums[0] <= target < nums[mid]:
                r = mid - 1
            else:  # 否则移动左指针 为 mid+1
                l = mid + 1
        # 否则 后半部分有序
        else:
            # 如果目标元素 在后半部分，就移动左指针为 mid+1
            if nums[mid] < target <= nums[len(nums) - 1]:
                l = mid + 1
            else: # 否则右指针为 mid - 1
                r = mid - 1
    return -1

target = 0
nums = [4,5,6,7,0,1,2]
print( search(nums, target) )  # 4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

# 22.数组中的第K个最大元素

数组中的第K个最大元素 (opens new window)

在未排序的数组中找到第 k 个最大的元素
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素

例：寻找第二大元素
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

1
2
3

# 22.1 heapq模块找到前十大元素

1、取列表前10个元素建立一个小根堆，堆顶就是目前的10大的数（建立小根堆）
2、依次向后遍历原列表，对于列表中的元素，如果小于堆顶，则忽略该元素，如果大于堆顶，则将堆顶更换为该元素，并且对堆进行依次调整
3、遍历列表所有元素后，倒序弹出堆顶

def findKthLargest(nums, k):
    import heapq
    ret = heapq.nlargest(k, nums)  # 使用heapq模块建立一个K大的堆
    return ret[k-1]

nums = [3,2,1,5,6,4]
print( findKthLargest(nums,2) )

1
2
3
4
5
6
7

# 22.2 自己实现堆排实现

# !/usr/bin/env python
# -*- coding:utf-8 -*-
class Solution:
	def sift(self, data, low, high):
		'''  构造小根堆 : 堆中某节点的值总是不小于父节点的值
		:param data: 传入的待排序的列表
		:param low:  需要进行排序的那个小堆的根对应的号
		:param high: 需要进行排序那个小堆最大的那个号
		:return:
		'''
		root = low  # i最开始创建堆时是最后一个有孩子的父亲对应根的号
		child = 2 * root + 1  # j子堆左孩子对应的号
		tmp = data[root]  # tmp是子堆中原本根的值（拿出最高领导）
		while child <= high:  # 只要没到子堆的最后（每次向下找一层）孩子在堆里
			if child + 1 <= high and data[child] > data[child + 1]:  # 如果有右孩纸，且比左孩子更小
				child += 1
			if tmp > data[child]:  # 如果孩子还比子堆原有根的值tmp小，就将孩子放到子堆的根
				data[root] = data[child]  # 孩子成为子堆的根
				root = child   # 孩子成为新父亲（向下再找一层）
				child = 2 * root + 1  # 新孩子  （此时如果j<=high证明还有孩，继续找）
			else:
				break      # 如果能干就跳出循环就会留出一个空位
		data[root] = tmp   # 最高领导放到父亲位置

	def topn(self, nums, k):
		# 1、构建10个数量的小根堆
		heap = nums[0:k]  # 先取10个元素
		for i in range(k // 2 - 1, -1, -1):  # 使用这10个元素构建出一个小根堆
			self.sift(heap, i, k - 1)

		# 2、找出li中前10大元素放入heap中
		for i in range(k, len(nums)):  # 依次取出剩下的元素
			if nums[i] > heap[0]:  # 如果新元素比堆顶元素大
				heap[0] = nums[i]  # 就将新元素替换堆顶元素
				self.sift(heap, 0, k - 1)  # 重新构建小根堆

		# 3、利用堆排将这个小根堆倒序排列
		for i in range(k - 1, -1, -1):  # 上面的for循环已经找出了前十大元素，这里是排序
			heap[0], heap[i] = heap[i], heap[0]
			self.sift(heap, 0, i - 1)
		print(heap)  # [6, 5]
		return heap[k - 1]


nums = [3, 2, 1, 5, 6, 4]
print(Solution().topn(nums, 2))  # 5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

编辑

上次更新: 2022/09/21, 11:19:29

← 04.算法模型 02.字符串→

01.数组

# 01.求两数之和

# 1.1 python答案

# 1.2 golang答案

# 02.最大子序和

# 2.1 题目描述

# 2.2 python

# 2.3 golang

# 03.买卖股票的最佳时机

# 3.1 题目要求

# 3.2 python

# 3.3 golang

# 04.买卖股票最大亏损

# 4.1 题目要求

# 4.2 python

# 05.合并两个有序数组

# 5.1 题目说明

# 5.2 普通合并方案

# 5.3 python双指针

# 5.4 golang双指针

# 06.数组中重复的数字

# 6.1 题目描述

# 6.2 python

# 6.2 golang

# 07.删除有序数组中重复项

# 7.1 题目描述

# 7.2 python

# 7.3 golang

# 08.两数之和 II

# 8.1 题目描述

# 8.2 python

# 8.3 golang

# 09.多数元素

# 9.1 题目描述

# 9.2 解题思路

# 10.旋转数组的最小数字

# 10.1 题目描述

# 10.2 python

# 10.3 golang

# 11.两个数组的交集

# 11.1 题目描述

# 11.2 python

# 11.3 golang

# 12.加一

# 12.1 题目描述

# 12.2 python

# 12.3 golang

# 13.和为s的连续正数序列

# 13.1 题目描述

# 13.2 python滑动窗口

# 13.3 golang滑动窗口

# 14.两个数组的交集 II

# 14.1 题目描述

# 两个数组的交集 II (opens new window)

# 14.2 python字典方法

# 14.3 python排序双指针

# 14.4 golang排序双指针

# 15.找到所有数组中消失的数字

# 15.1 题目描述

# 15.2 python

# 16.列表去重

# 16.1 python

# 16.2 golang

# 17.实现enumerate函数

# 18.列表连续相同数据放一起

# 18.1 题目要求

# 18.2 解题思路

# 19.盛最多水的容器

# 19.1 题目描述

# 19.2 python

# 19.3 golang

# 20.合并区间

# 20.1 题目说明

# 20.2 解题思路

# 21.搜索旋转排序数组

# 21.1 题目描述

# 21.2 解题思路

# 22.数组中的第K个最大元素

# 22.1 heapq模块找到前十大元素

# 22.2 自己实现堆排实现