欢迎关注我的微信公众号【万能的小江江】
部分题目/题解from Leetcode，侵删
题1-217. 存在重复元素
217. 存在重复元素
给定一个整数数组，判断是否存在重复元素。
如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
示例 1:
输入: [1,2,3,1]
输出: true
示例 2:
输入: [1,2,3,4]
输出: false
示例 3:
输入: [1,1,1,3,3,4,3,2,4,2]
输出: true题解1-map or 哈希表？
func containsDuplicate(nums []int) bool {
set := map[int]struct{}{}
for _, v := range nums {
if _, has := set[v]; has {
return true
}
set[v] = struct{}{}
}
return false
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/contains-duplicate/solution/cun-zai-zhong-fu-yuan-su-by-leetcode-sol-iedd/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。xxxxxxxxxx func containsDuplicate(nums []int) bool { set := map[int]struct{}{} for _, v := range nums { if _, has := set[v]; has { return true } set[v] = struct{}{} } return false}作者：LeetCode-Solution链接：https://leetcode-cn.com/problems/contains-duplicate/solution/cun-zai-zhong-fu-yuan-su-by-leetcode-sol-iedd/来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。func containsDuplicate(nums []int) bool { Map := make(map[int]int) for i := 0; i < len(nums); i++ { if _, ok := Map[nums[i]]; ok == false { Map[nums[i]] = nums[i] } else { return true } } return false}
题解2-排序
func containsDuplicate(nums []int) bool {
sort.Ints(nums)
for i := 1; i < len(nums); i++ {
if nums[i] == nums[i-1] {
return true
}
}
return false
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/contains-duplicate/solution/cun-zai-zhong-fu-yuan-su-by-leetcode-sol-iedd/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
题2-53. 最大子序和
53. 最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [0]
输出：0
示例 4：
输入：nums = [-1]
输出：-1
示例 5：
输入：nums = [-100000]
输出：-100000
提示：
1 <= nums.length <= 105
-104 <= nums[i] <= 104
进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。题解1-动态规划
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] += nums[i-1]
}
if nums[i] > max {
max = nums[i]
}
}
return max
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。题解2-分治
func maxSubArray(nums []int) int {
return get(nums, 0, len(nums) - 1).mSum;
}
func pushUp(l, r Status) Status {
iSum := l.iSum + r.iSum
lSum := max(l.lSum, l.iSum + r.lSum)
rSum := max(r.rSum, r.iSum + l.rSum)
mSum := max(max(l.mSum, r.mSum), l.rSum + r.lSum)
return Status{lSum, rSum, mSum, iSum}
}
func get(nums []int, l, r int) Status {
if (l == r) {
return Status{nums[l], nums[l], nums[l], nums[l]}
}
m := (l + r) >> 1
lSub := get(nums, l, m)
rSub := get(nums, m + 1, r)
return pushUp(lSub, rSub)
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
type Status struct {
lSum, rSum, mSum, iSum int
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。题3-1.两数之和
1. 两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
提示：
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案
进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？题解1-暴力枚举 时间复杂度高
func twoSum(nums []int, target int)[]int {
for i,v1 := range nums{
for j := i+1;j < len(nums);j++{
if v1+nums[j] == target{
return []int{i, j}
}
}
}
return nil
}题解2-哈希表
func twoSum(nums []int, target int) []int {
hashTable := map[int]int{}
for i, x := range nums {
if p, ok := hashTable[target-x]; ok {
return []int{p, i}
}
hashTable[x] = i
}
return nil
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。题4-88.合并两个有序数组
88. 合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
示例 2：
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。
示例 3：
输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
提示：
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[j] <= 109
进阶：你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？题解1-合并后排序 自己写的
func merge(nums1 []int, m int, nums2 []int, n int) {
x := 0
for i:=m;i < m+n;i++{
nums1[i] = nums2[x]
x++
}
sort.Ints(nums1)
}
//冒泡排序
func merge(nums1 []int, m int, nums2 []int, n int) {
x := 0
for i := m;i < m+n;i++{
nums1[i] = nums2[x]
x++
}
for a := 0;a < len(nums1);a++{
for b := 0;b < len(nums1)-1-a;b++{
if nums1[b] > nums1[b+1]{ //都是以内层的b为准，外层a只是控制总的次数，内层b是比较次数
temp := nums1[b]
nums1[b] = nums1[b+1]
nums1[b+1] = temp
}
}
}
}题解2-copy合并后排序
这种方法底层应该和上面是一样的
func merge(nums1 []int, m int, nums2 []int, _ int) {
copy(nums1[m:], nums2)
sort.Ints(nums1)
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/merge-sorted-array/solution/he-bing-liang-ge-you-xu-shu-zu-by-leetco-rrb0/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。题解3-双指针
func merge(nums1 []int, m int, nums2 []int, n int) {
sorted := make([]int, 0, m+n)
p1, p2 := 0, 0
for {
if p1 == m {
sorted = append(sorted, nums2[p2:]...)
break
}
if p2 == n {
sorted = append(sorted, nums1[p1:]...)
break
}
if nums1[p1] < nums2[p2] {
sorted = append(sorted, nums1[p1])
p1++
} else {
sorted = append(sorted, nums2[p2])
p2++
}
}
copy(nums1, sorted)
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/merge-sorted-array/solution/he-bing-liang-ge-you-xu-shu-zu-by-leetco-rrb0/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。- 因为都是按照顺序排列的
- 先make一个sorted切片
- 这个for循环，谁小，谁先进sorted。直到指针指到最后一个数字。再把另外一个剩下的都append到sorted
- 最后用sorted覆盖nums1
题解4-逆向双指针
func merge(nums1 []int, m int, nums2 []int, n int) {
for p1, p2, tail := m-1, n-1, m+n-1; p1 >= 0 || p2 >= 0; tail-- {
var cur int
if p1 == -1 {
cur = nums2[p2]
p2--
} else if p2 == -1 {
cur = nums1[p1]
p1--
} else if nums1[p1] > nums2[p2] {
cur = nums1[p1]
p1--
} else {
cur = nums2[p2]
p2--
}
nums1[tail] = cur
}
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/merge-sorted-array/solution/he-bing-liang-ge-you-xu-shu-zu-by-leetco-rrb0/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。题5-兴业银行笔试
求一个数组中出现2次及以上的数，用字符串输出题解1
package main
import (
"fmt"
)
func findSame(a [8]int) []int{
n := len(a)
res := make([]int,0)
for _,val := range a{
a[val%(n+1)-1] += (n+1)
}
for index,val2 := range a{
if val2/(n+1) == 2{
res = append(res,index+1)
}
}
return res
}
func main(){
var a [8]int
for i := 0;i < 8;i++{
fmt.Scan(&a[i])
}
arr := findSame(a)
for j := 0;j < len(arr);j++{
fmt.Print(arr[j]," ")v
}
}
题6-350. 两个数组的交集 II
给定两个数组，编写一个函数来计算它们的交集。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]
示例 2:
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]
说明：
输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
我们可以不考虑输出结果的顺序。
进阶：
如果给定的数组已经排好序呢？你将如何优化你的算法？
如果 nums1 的大小比 nums2 小很多，哪种方法更优？
如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？题解1-排序+双指针
func intersect(nums1 []int, nums2 []int) []int {
sort.Ints(nums1)
sort.Ints(nums2)
var p1 int
var p2 int
intersect := []int{}
for p1 < len(nums1) && p2 < len(nums2){
if nums1[p1] < nums2[p2]{ //从小到大排序，这里nums1小，指针往后移动
p1++
} else if nums2[p2] < nums1[p1]{ //为啥这里要用else if
p2++
} else {
intersect = append(intersect,nums1[p1])
p1++
p2++
}
}
return intersect
}题解2-哈希表
func intersect(nums1 []int, nums2 []int) []int {
if len(nums1) > len(nums2) {
return intersect(nums2, nums1)
}
m := map[int]int{}
for _, num := range nums1 {
m[num]++
}
intersection := []int{}
for _, num := range nums2 {
if m[num] > 0 {
intersection = append(intersection, num)
m[num]--
}
}
return intersection
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/solution/liang-ge-shu-zu-de-jiao-ji-ii-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
