求合取余即可，余数就是答案。
Time complexity: O(n)
Space complexity: O(1)
|
1 2 3 4 5 6 |
class Solution { public: int minOperations(vector<int>& nums, int k) { return accumulate(begin(nums), end(nums), 0) % k; } }; |
Posts tagged as “sum”
Given a 0-indexed integer array nums, determine whether there exist two subarrays of length 2 with equal sum. Note that the two subarrays must begin at different indices.
Return true if these subarrays exist, and false otherwise.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [4,2,4] Output: true Explanation: The subarrays with elements [4,2] and [2,4] have the same sum of 6.
Example 2:
Input: nums = [1,2,3,4,5] Output: false Explanation: No two subarrays of size 2 have the same sum.
Example 3:
Input: nums = [0,0,0] Output: true Explanation: The subarrays [nums[0],nums[1]] and [nums[1],nums[2]] have the same sum of 0. Note that even though the subarrays have the same content, the two subarrays are considered different because they are in different positions in the original array.
Constraints:
2 <= nums.length <= 1000-109 <= nums[i] <= 109
Solution: Hashset
Use a hashset to track all the sums seen so far.
Time complexity: O(n)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 |
// Author: Huahua class Solution { public: bool findSubarrays(vector<int>& nums) { unordered_set<int> s; for (int i = 1; i < nums.size(); ++i) if (!s.emplace(nums[i] + nums[i - 1]).second) return true; return false; } }; |
You are given an integer array nums of length n, and an integer array queries of length m.
Return an array answer of length m where answer[i] is the maximum size of a subsequence that you can take from nums such that the sum of its elements is less than or equal to queries[i].
A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
Example 1:
Input: nums = [4,5,2,1], queries = [3,10,21] Output: [2,3,4] Explanation: We answer the queries as follows: - The subsequence [2,1] has a sum less than or equal to 3. It can be proven that 2 is the maximum size of such a subsequence, so answer[0] = 2. - The subsequence [4,5,1] has a sum less than or equal to 10. It can be proven that 3 is the maximum size of such a subsequence, so answer[1] = 3. - The subsequence [4,5,2,1] has a sum less than or equal to 21. It can be proven that 4 is the maximum size of such a subsequence, so answer[2] = 4.
Example 2:
Input: nums = [2,3,4,5], queries = [1] Output: [0] Explanation: The empty subsequence is the only subsequence that has a sum less than or equal to 1, so answer[0] = 0.
Constraints:
n == nums.lengthm == queries.length1 <= n, m <= 10001 <= nums[i], queries[i] <= 106
Solution: Sort + PrefixSum + Binary Search
Time complexity: O(nlogn + mlogn)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 |
// Author: Huahua class Solution { public: vector<int> answerQueries(vector<int>& nums, vector<int>& queries) { sort(begin(nums), end(nums)); partial_sum(begin(nums), end(nums), begin(nums)); vector<int> ans; for (int q : queries) ans.push_back(upper_bound(begin(nums), end(nums), q) - begin(nums)); return ans; } }; |
Problem
Solution 1: Range sum query
Assuming we can collect fruits in range [l, r], we need a fast query to compute the sum of those fruits.
Given startPos and k, we have four options:
1. move i steps to the left
2. move i steps to the left and k – i steps to the right.
3. move i steps to the right
4. move i steps to the right and k – i steps to the left.
We enumerate i steps and calculate maximum range [l, r] covered by each option, and collect all the fruit in that range.
Time complexity: O(m + k)
Space complexity: O(m)
where m = max(max(pos), startPos)
C++
|
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 |
// Author: Huahua class Solution { public: int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) { const int m = max(startPos, (*max_element(begin(fruits), end(fruits)))[0]); vector<int> sums(m + 2); for (int i = 0, j = 0; i <= m; ++i) { sums[i + 1] += sums[i]; while (j < fruits.size() && fruits[j][0] == i) sums[i + 1] += fruits[j++][1]; } int ans = 0; for (int s = 0; s <= k; ++s) { if (startPos - s >= 0) { int l = startPos - s; int r = min(max(startPos, l + (k - s)), m); ans = max(ans, sums[r + 1] - sums[l]); } if (startPos + s <= m) { int r = startPos + s; int l = max(0, min(startPos, r - (k - s))); ans = max(ans, sums[r + 1] - sums[l]); } } return ans; } }; |
Solution 2: Sliding Window
Maintain a window [l, r] such that the steps to cover [l, r] from startPos is less or equal to k.
Time complexity: O(n)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua class Solution { public: int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) { auto steps = [&](int l, int r) { if (r <= startPos) return startPos - l; else if (l >= startPos) return r - startPos; else return min(startPos + r - 2 * l, 2 * r - startPos - l); }; int ans = 0; for (int r = 0, l = 0, cur = 0; r < fruits.size(); ++r) { cur += fruits[r][1]; while (l <= r && steps(fruits[l][0], fruits[r][0]) > k) cur -= fruits[l++][1]; ans = max(ans, cur); } return ans; } }; |
You are given two positive integer arrays nums1 and nums2, both of length n.
The absolute sum difference of arrays nums1 and nums2 is defined as the sum of |nums1[i] - nums2[i]| for each 0 <= i < n (0-indexed).
You can replace at most one element of nums1 with any other element in nums1 to minimize the absolute sum difference.
Return the minimum absolute sum difference after replacing at most oneelement in the array nums1. Since the answer may be large, return it modulo 109 + 7.
|x| is defined as:
xifx >= 0, or-xifx < 0.
Example 1:
Input: nums1 = [1,7,5], nums2 = [2,3,5]
Output: 3
Explanation: There are two possible optimal solutions:
- Replace the second element with the first: [1,7,5] => [1,1,5], or
- Replace the second element with the third: [1,7,5] => [1,5,5].
Both will yield an absolute sum difference of |1-2| + (|1-3| or |5-3|) + |5-5| = 3.
Example 2:
Input: nums1 = [2,4,6,8,10], nums2 = [2,4,6,8,10] Output: 0 Explanation: nums1 is equal to nums2 so no replacement is needed. This will result in an absolute sum difference of 0.
Example 3:
Input: nums1 = [1,10,4,4,2,7], nums2 = [9,3,5,1,7,4]
Output: 20
Explanation: Replace the first element with the second: [1,10,4,4,2,7] => [10,10,4,4,2,7].
This yields an absolute sum difference of |10-9| + |10-3| + |4-5| + |4-1| + |2-7| + |7-4| = 20
Constraints:
n == nums1.lengthn == nums2.length1 <= n <= 1051 <= nums1[i], nums2[i] <= 105
Solution: Binary Search
Greedy won’t work, e.g. finding the max diff pair and replace it. Counter example:
nums1 = [7, 5], nums2 = [1, -2]
pair1 = abs(7 – 1) = 6
pair2 = abs(5 – (-2)) = 7
If we replace 5 with 7, we got pair2′ = abs(7 – (-2)) = 9 > 7.
Every pair of numbers can be the candidate, we just need to find the closest number for each nums2[i].
Time complexity: O(nlogn)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Solution { public: int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) { constexpr int kMod = 1e9 + 7; const int n = nums1.size(); long ans = 0; int gain = 0; set<int> s(begin(nums1), end(nums1)); for (int i = 0; i < n; ++i) { const int diff = abs(nums1[i] - nums2[i]); ans += diff; if (diff <= gain) continue; auto it = s.lower_bound(nums2[i]); if (it != s.end()) gain = max(gain, diff - abs(*it - nums2[i])); if (it != s.begin()) gain = max(gain, diff - abs(*prev(it) - nums2[i])); } return (ans - gain) % kMod; } }; |