Open Draymonders opened 4 years ago
题目一般是要求 nums[i] + nums[j] == target, 或者( nums[i] + nums[j] )% target == 0
nums[i] + nums[j] == target
( nums[i] + nums[j] )% target == 0
或者根据条件得出的前缀和 sum[j] - sum[i] == target
sum[j] - sum[i] == target
本质上都是求pair<int, int>满足一个条件, 能想到的就是 枚举i, j，来达到条件，复杂度O(n^2)
pair<int, int>
O(n^2)
有个O(n)的思路就是，建一个unordered_map<int, int> mp
O(n)
unordered_map<int, int> mp
mp[x]
x
res += mp[target - nums[i]] res += mp[60 - nums[i] % 60]; res += mp[target - sum[i]]
leetcode 1
leetcode 1010
leetcode 1248
题目
题目一般是要求
nums[i] + nums[j] == target, 或者( nums[i] + nums[j] )% target == 0或者根据条件得出的前缀和
sum[j] - sum[i] == target套路
本质上都是求
pair<int, int>满足一个条件, 能想到的就是 枚举i, j，来达到条件，复杂度O(n^2)有个
O(n)的思路就是，建一个unordered_map<int, int> mpmp[x]表示在位置i之前，x出现了多少次题目汇总
leetcode 1leetcode 1010leetcode 1248leetcode 1248