给定一个整数数组 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 <= 10<sup>4</sup>
-10<sup>9</sup> <= nums[i] <= 10<sup>9</sup>
-10<sup>9</sup> <= target <= 10<sup>9</sup>
进阶:你可以想出一个时间复杂度小于 O(n<sup>2</sup>)
的算法吗?
func twoSum(nums []int, target int) []int { for i,x := range nums { for j := i + 1; j < len(nums); j++ { if x+nums[j] == target { return []int{i,j} } } } return nil }
给定一个已按照**非递减顺序排列 ** 的整数数组 numbers
,请你从数组中找出两个数满足相加之和等于目标数 target
。
函数应该以长度为 2
的整数数组的形式返回这两个数的下标值_。_numbers
的下标 从 1 开始计数 ,所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length
。
你可以假设每个输入 只对应唯一的答案 ,而且你 不可以 重复使用相同的元素。
示例 1:
输入:numbers = [2,7,11,15], target = 9 输出:[1,2] 解释:2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
示例 2:
输入:numbers = [2,3,4], target = 6 输出:[1,3]
示例 3:
输入:numbers = [-1,0], target = -1 输出:[1,2]
提示:
2 <= numbers.length <= 3 * 10<sup>4</sup>
-1000 <= numbers[i] <= 1000
numbers
按 非递减顺序 排列-1000 <= target <= 1000
#双指针
func twoSum(numbers []int, target int) []int { left,right := 0, len(numbers) - 1 for left < right { sum := numbers[left] + numbers [right] if sum == target { return []int{left + 1, right + 1} } else if sum < target { left++ } else { right-- } } return []int{-1,-1} }
给你一个包含 n
个整数的数组 nums
,判断 nums
中是否存在三个元素 _a,b,c ,_使得 a + b + c = 0 ?请你找出所有和为 0
且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例 1:
输入:nums = [-1,0,1,2,-1,-4] 输出:[[-1,-1,2],[-1,0,1]]
示例 2:
输入:nums = [] 输出:[]
示例 3:
输入:nums = [0] 输出:[]
提示:
0 <= nums.length <= 3000
-10<sup>5</sup> <= nums[i] <= 10<sup>5</sup>
#三指针
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> ans; // 先排序 int n = nums.size(); sort(nums.begin(), nums.end()); // 定义首指针==target for (int i = 0; i < n; i++) { if ( i > 0 && nums[i] == nums[i-1]) continue; int k = n - 1; // 内层首指针 int target = -nums[i]; for (int j = i + 1; j < n; j++) // 内层尾指针 { if( j > i + 1 && nums[j] == nums[j-1]) continue; while (j < k && nums[j] + nums[k] > target) { // 遍历尾指针,找合适序列 --k; } // 当前i不满足 if(j == k) { break; } // 得到符合条件序列 if(nums[j] + nums[k] == target) { ans.push_back({nums[i],nums[j],nums[k]}); } } } return ans; } };
给你一个由 n
个整数组成的数组 nums
,和一个目标值 target
。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]]
(若两个四元组元素一一对应,则认为两个四元组重复):
0 <= a, b, c, d < n
a
、b
、c
和 d
互不相同nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
示例 1:
输入:nums = [1,0,-1,0,-2,2], target = 0 输出:[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2:
输入:nums = [2,2,2,2,2], target = 8 输出:[[2,2,2,2]]
提示:
1 <= nums.length <= 200
-10<sup>9</sup> <= nums[i] <= 10<sup>9</sup>
-10<sup>9</sup> <= target <= 10<sup>9</sup>
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> ans; int n = nums.size(); if(n < 4) return ans; sort(nums.begin(), nums.end()); for (int i = 0; i < n - 3; i++) { if (i > 0 && nums[i] == nums[i-1]) continue; if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) { break; } if ((long) nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) { continue; } for (int j = i + 1; j < n - 2; j++) { if (j > i + 1 && nums[j] == nums[j-1]) continue; if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) { break; } if ((long) nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target) { continue; } // 最内层首尾指针 int m = n - 1, k = j + 1; while(k < m) { int sum = nums[i] + nums[j] + nums[k] + nums[m]; if (sum == target) { ans.push_back({nums[i], nums[j], nums[k], nums[m]}); while (k < m && nums[k] == nums[k + 1]) { k++; } k++; while (k < m && nums[m] == nums[m - 1]) { m--; } m--; } else if (sum < target) { k++; } else { m--; } } } } return ans; } };
斐波那契数,通常用 F(n)
表示,形成的序列称为 斐波那契数列 。该数列由 0
和 1
开始,后面的每一项数字都是前面两项数字的和。也就是:
F(0) = 0,F(1) = 1 F(n) = F(n - 1) + F(n - 2),其中 n > 1
给你 n
,请计算 F(n)
。
示例 1:
输入:2 输出:1 解释:F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2:
输入:3 输出:2 解释:F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3:
输入:4 输出:3 解释:F(4) = F(3) + F(2) = 2 + 1 = 3
提示:
0 <= n <= 30
func fib(n int) int { if n == 0 { return 0 } else if n == 1 { return 1 } else { return fib(n-2) + fib(n-1) } }
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。
示例 1:
输入: 2 输出: 2 解释: 有两种方法可以爬到楼顶。 1\. 1 阶 + 1 阶 2\. 2 阶
示例 2:
输入: 3 输出: 3 解释: 有三种方法可以爬到楼顶。 1\. 1 阶 + 1 阶 + 1 阶 2\. 1 阶 + 2 阶 3\. 2 阶 + 1 阶
func climbStairs(n int) int { if n <= 2 { return n } pre1,pre2 := 2,1 for i := 2; i < n; i++ { cur := pre1 + pre2 pre2 = pre1 pre1 = cur } return pre1 }
给你一个整数数组 nums
,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
子数组 是数组中的一个连续部分。
示例 1:
输入:nums = [-2,1,-3,4,-1,2,1,-5,4] 输出:6 解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。
示例 2:
输入:nums = [1] 输出:1
示例 3:
输入:nums = [5,4,-1,7,8] 输出:23
提示:
1 <= nums.length <= 10<sup>5</sup>
-10<sup>4</sup> <= nums[i] <= 10<sup>4</sup>
进阶:如果你已经实现复杂度为 O(n)
的解法,尝试使用更为精妙的 分治法 求解。
#动态规划
func maxSubArray(nums []int) int { sum := 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] > sum { sum = nums[i] } } return sum }
给你一个 只包含正整数 的 非空 数组 nums
。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
示例 1:
输入:nums = [1,5,11,5] 输出:true 解释:数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2:
输入:nums = [1,2,3,5] 输出:false 解释:数组不能分割成两个元素和相等的子集。
提示:
1 <= nums.length <= 200
1 <= nums[i] <= 100
#动态规划 #背包问题 #difficult
func canPartition(nums []int) bool { n := len(nums) if n < 2 { return false } sum, maxNum := 0,0 for _,num := range nums { sum += num if num > maxNum { maxNum = num } } // 判断总和是不是奇数 if sum%2 != 0 { return false } target := sum / 2 if target < maxNum { return false } dp := make([]bool, target+1) dp[0] = true for i := 0; i < n; i++ { v := nums[i] for j := target; j >= v; j-- { dp[j] = dp[j] || dp[j-v] } } return dp[target] }
给你一个整数数组 coins
,表示不同面额的硬币;以及一个整数 amount
,表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1
。
你可以认为每种硬币的数量是无限的。
示例 1:
输入:coins = [1, 2, 5], amount = 11 输出:3 解释:11 = 5 + 5 + 1
示例 2:
输入:coins = [2], amount = 3 输出:-1
示例 3:
输入:coins = [1], amount = 0 输出:0
示例 4:
输入:coins = [1], amount = 1 输出:1
示例 5:
输入:coins = [1], amount = 2 输出:2
提示:
1 <= coins.length <= 12
1 <= coins[i] <= 2<sup>31</sup> - 1
0 <= amount <= 10<sup>4</sup>
#动态规划
func coinChange(coins []int, amount int) int { dp := make([]int, amount + 1) dp[0] = 0 // 初始化为math.MaxInt32 for j := 1; j <= amount; j++ { dp[j] = math.MaxInt32 } for i := 0; i < len(coins); i++ { for j := coins[i]; j <= amount ; j++ { if dp[j-coins[i]] != math.MaxInt32 { dp[j] = min(dp[j], dp[j-coins[i]]+1) } } } // 没找到能装满背包的, 就返回-1 if dp[amount] == math.MaxInt32 { return -1 } return dp[amount] } func min(a, b int) int { if a < b{ return a } return b }
给定一个只包括 '('
,')'
,'{'
,'}'
,'['
,']'
的字符串 s
,判断字符串是否有效。
有效字符串需满足:
示例 1:
输入:s = "()" 输出:true
示例 2:
输入:s = "()[]{}" 输出:true
示例 3:
输入:s = "(]" 输出:false
示例 4:
输入:s = "([)]" 输出:false
示例 5:
输入:s = "{[]}" 输出:true
提示:
1 <= s.length <= 10<sup>4</sup>
s
仅由括号 '()[]{}'
组成#栈
func isValid(s string) bool { n := len(s) if n % 2 == 1 { return false } pairs := map[byte]byte { ')':'(', ']':'[', '}':'{', } stack := []byte{} for i := 0; i < n; i++ { if pairs[s[i]] > 0 { if len(stack) == 0 || stack[len(stack)-1] != pairs[s[i]] { return false } stack = stack[:len(stack)-1] } else { stack = append(stack,s[i]) } } return len(stack) == 0 }