两数之和
两数之和
解题思路
暴力破解，遍历数组中所有的两数之和，得到和为目标值的两个数组元素，时间复杂度达O(n^2)
本题是要找到数组中的两个数，使它们的和为目标值。可以利用Hash表记录已经访问过的元素，在遍历时去查找Hash表中是否已经有访问过的元素，使得它加上当前访问元素的和为目标值。这样的算法时间复杂度为O(n)，空间复杂度为O(n)
解题代码
- 暴力破解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| func twoSum(nums []int, target int) []int {
result := make([]int, 2)
loop:
for i := 0; i < len(nums)-1; i++ {
for j := i+1; j < len(nums); j++ {
if nums[i] + nums[j] == target {
result[0] = i
result[1] = j
break loop
}
}
}
return result
}
|
- hash map
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| func twoSum(nums []int, target int) []int {
hashmap := make(map[int]int)
result := make([]int, 2)
for index, val := range nums {
if preIndex,ok := hashmap[target-val]; ok {
result[0] = preIndex
result[1] = index
break
} else {
hashmap[val] = index
}
}
return result
}
|
最大子数组和
最大子数组和
解题思路
- 贪心算法，在遍历数组的过程中记录部分和。若部分和小于0，则不论下一个元素是多少，它们之和都小于下一个元素自身。若部分和大于等于0，则部分和加上下一个元素有可能大于当前最大子数组之和。
- 动态规划法，令
dp[i]表示nums中以nums[i]结尾的最大子序列之和，dp[i] = max { dp[i-1]+ nums[i], nums[i] }，最大子序列之和即为dp[i]的最大值。因为dp[i]只用到了dp[i-1]，可以用int型变量代替dp数组，故空间复杂度可以从O(n^2)降为O(1)，时间复杂度为O(n)
解题代码
- 贪心算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| func maxSubArray(nums []int) int {
maxSum := nums[0]
var partSum int
for i:= 0; i < len(nums); i++ {
partSum += nums[i]
if partSum > maxSum {
maxSum = partSum
}
if partSum < 0 {
partSum = 0
}
}
return maxSum
}
|
- 动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| func maxSubArray(nums []int) int {
maxSum := nums[0]
dp := nums[0]
for i := 1; i < len(nums); i++ {
dp = max(dp+nums[i], nums[i])
maxSum = max(dp, maxSum)
}
return maxSum
}
func max(n1, n2 int) int {
if n1 > n2 {
return n1
} else {
return n2
}
}
|
三数之和
三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
解题思路
排序+双指针：
- 首先对数组进行排序
- 设立左指针
left和右指针right指向nums[i]后面的两端，若：
nums[i]与nums[i-1]相同，则i++nums[i] + nums[right] + nums[left] > 0，说明nums[right]过大，right--nums[i] + nums[right] + nums[left] < 0，说明nums[left]过大，left++nums[i] + nums[right] + nums[left] == 0
nums[left-1] == nums[left]，左指针与上一个指向的值重复，跳过，left++nums[right] == nums[right+1]，右指针与上一个指向的值重复，跳过，right--- 否则将
nums[i], nums[right], nums[left]加入结果集
解题代码
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
| func threeSum(nums []int) [][]int {
n := len(nums)
result := make([][]int, 0)
sort.Ints(nums)
for i := 0; i < n-2; i++ {
if i > 0 && nums[i-1] == nums[i] {
continue
}
left, right := i+1, n-1
for left < right {
if nums[i] + nums[right] + nums[left] > 0 {
right--
} else if nums[i] + nums[right] + nums[left] < 0 {
left++
} else {
if left > i+1 && nums[left-1] == nums[left] {
left++
} else if right < n-1 && nums[right] == nums[right+1] {
right--
} else {
result = append(result, []int{nums[i], nums[right], nums[left]})
left++
right--
}
}
}
}
return result
}
|