目录
Arrays and strings
Two pointers
Example 1: Given a string s, return true if it is a palindrome, false otherwise.
A string is a palindrome if it reads the same forward as backward. That means, after reversing it, it is still the same string. For example: “abcdcba”, or “racecar”.
bool checkIfPalindrome(string s) {
int left = 0;
int right = s.size() - 1;
while (left < right) {
if (s[left] != s[right]) {
return false;
}
left++;
right--;
}
return true;
}Given a sorted array of unique integers and a target integer, return true if there exists a pair of numbers that sum to target, false otherwise. This problem is similar to Two Sum. (In Two Sum, the input is not sorted).
For example, given nums = [1, 2, 4, 6, 8, 9, 14, 15] and target = 13, return true because 4 + 9 = 13.
bool checkForTarget(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left < right) {
// curr is the current sum
int curr = nums[left] + nums[right];
if (curr == target) {
return true;
}
if (curr > target) {
right--;
} else {
left++;
}
}
return false;
}Example 3: Given two sorted integer arrays arr1 and arr2, return a new array that combines both of them and is also sorted.
vector<int> combine(vector<int>& arr1, vector<int>& arr2) {
// ans is the answer
vector<int> ans;
int i = 0, j = 0;
while (i < arr1.size() && j < arr2.size()) {
if (arr1[i] < arr2[j]) {
ans.push_back(arr1[i]);
i++;
} else {
ans.push_back(arr2[j]);
j++;
}
}
while (i < arr1.size()) {
ans.push_back(arr1[i]);
i++;
}
while (j < arr2.size()) {
ans.push_back(arr2[j]);
j++;
}
return ans;
}Example 4: 392. Is Subsequence.
Given two strings s and t, return true if s is a subsequence of t, or false otherwise.
A subsequence of a string is a sequence of characters that can be obtained by deleting some (or none) of the characters from the original string, while maintaining the relative order of the remaining characters. For example, “ace” is a subsequence of “abcde” while “aec” is not.
class Solution {
public:
bool isSubsequence(string s, string t) {
int i = 0, j = 0;
while (i < s.size() && j < t.size()) {
if (s[i] == t[j]) {
i++;
}
j++;
}
return i == s.size();
}
};Write a function that reverses a string. The input string is given as an array of characters s.
You must do this by modifying the input array in-place with O(1) extra memory.
class Solution {
public:
void reverseString(vector<char>& s) {
int i = 0, j = s.size()-1;
char c;
while(i<j) {
c = s[i];
s[i] = s[j];
s[j] = c;
i++;
j--;
}
}
};Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
vector<int> result(nums.size(),5);
int i = 0;
int j = nums.size()-1;
int k = nums.size()-1;
int square_left = nums[i]*nums[i];
int square_right = nums[j]*nums[j];
while(i<j) {
if(square_left>square_right) {
result[k] = square_left;
i++;
square_left = nums[i]*nums[i];
}
else {
result[k] = square_right;
j--;
square_right = nums[j]*nums[j];
}
k--;
}
result[k] = square_left;
return result;
}
};Sliding window
Example 1: Given an array of positive integers nums and an integer k, find the length of the longest subarray whose sum is less than or equal to k. This is the problem we have been talking about above. We will now formally solve it.
int findLength(vector<int>& nums, int k) {
// curr is the current sum of the window
int left = 0, curr = 0, ans = 0;
for (int right = 0; right < nums.size(); right++) {
curr += nums[right];
while (curr > k) {
curr -= nums[left];
left++;
}
ans = max(ans, right - left + 1);
}
return ans;
}Example 2: You are given a binary string s (a string containing only “0” and “1”). You may choose up to one “0” and flip it to a “1”. What is the length of the longest substring achievable that contains only “1”?
For example, given s = “1101100111”, the answer is 5. If you perform the flip at index 2, the string becomes 1111100111.
int findLength(string s) {
// curr is the current number of zeros in the window
int left = 0, curr = 0, ans = 0;
for (int right = 0; right < s.size(); right++) {
if (s[right] == '0') {
curr++;
}
while (curr > 1) {
if (s[left] == '0') {
curr--;
}
left++;
}
ans = max(ans, right - left + 1);
}
return ans;
}Example 3: 713. Subarray Product Less Than K.
Given an array of positive integers nums and an integer k, return the number of subarrays where the product of all the elements in the subarray is strictly less than k.
For example, given the input nums = [10, 5, 2, 6], k = 100, the answer is 8. The subarrays with products less than k are:
[10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]
class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
if (k <= 1) {
return 0;
}
int ans = 0, left = 0, curr = 1;
for (int right = 0; right < nums.size(); right++) {
curr *= nums[right];
while (curr >= k) {
curr /= nums[left];
left++;
}
ans += right - left + 1;
}
return ans;
}
};Example 4: Given an integer array nums and an integer k, find the sum of the subarray with the largest sum whose length is k.
int findBestSubarray(vector<int>& nums, int k) {
int curr = 0;
for (int i = 0; i < k; i++) {
curr += nums[i];
}
int ans = curr;
for (int i = k; i < nums.size(); i++) {
curr += nums[i] - nums[i - k];
ans = max(ans, curr);
}
return ans;
}You are given an integer array nums consisting of n elements, and an integer k.
Find a contiguous subarray whose length is equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10-5 will be accepted.
class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
int curr = 0;
for(int i=0; i<k; i++) {
curr += nums[i];
}
int ans = curr;
for(int i=k; i<nums.size(); i++) {
curr += nums[i]-nums[i-k];
ans = max(ans, curr);
}
return (double)ans/k;
}
};Given a binary array nums and an integer k, return the maximum number of consecutive 1’s in the array if you can flip at most k 0’s.
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int left=0, curr=0, ans=0, n=nums.size();
for(int right=0; right<n; right++) {
if(nums[right]==0) {
curr++;
}
while(curr>k) {
if(nums[left]==0) {
curr--;
}
left++;
}
ans = max(ans, right-left+1);
}
return ans;
}
};Prefix sum
Example 1: Given an integer array nums, an array queries where queries[i] = [x, y] and an integer limit, return a boolean array that represents the answer to each query. A query is true if the sum of the subarray from x to y is less than limit, or false otherwise.
For example, given nums = [1, 6, 3, 2, 7, 2], queries = [[0, 3], [2, 5], [2, 4]], and limit = 13, the answer is [true, false, true]. For each query, the subarray sums are [12, 14, 12].
vector<bool> answerQueries(vector<int>& nums, vector<vector<int>>& queries, int limit) {
vector<int> prefix = {nums[0]};
for (int i = 1; i < nums.size(); i++) {
prefix.push_back(prefix.back() + nums[i]);
}
vector<bool> ans;
for (vector<int>& query: queries) {
int x = query[0], y = query[1];
int curr = prefix[y] - prefix[x] + nums[x];
ans.push_back(curr < limit);
}
return ans;
}Example 2: 2270. Number of Ways to Split Array
Given an integer array nums, find the number of ways to split the array into two parts so that the first section has a sum greater than or equal to the sum of the second section. The second section should have at least one number.
class Solution {
public:
int waysToSplitArray(vector<int>& nums) {
int n = nums.size();
vector<long> prefix = {nums[0]};
for (int i = 1; i < n; i++) {
prefix.push_back(nums[i] + prefix.back());
}
int ans = 0;
for (int i = 0; i < n - 1; i++) {
long leftSection = prefix[i];
long rightSection = prefix.back() - prefix[i];
if (leftSection >= rightSection) {
ans++;
}
}
return ans;
}
};class Solution {
public:
int waysToSplitArray(vector<int>& nums) {
int ans = 0;
long leftSection = 0;
long total = 0;
for (int num: nums) {
total += num;
}
for (int i = 0; i < nums.size() - 1; i++) {
leftSection += nums[i];
long rightSection = total - leftSection;
if (leftSection >= rightSection) {
ans++;
}
}
return ans;
}
};Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).
Return the running sum of nums.
class Solution {
public:
vector<int> runningSum(vector<int>& nums) {
int n = nums.size();
vector<int> prefix(n,nums[0]);
for(int i=1; i<n; i++) {
prefix[i] = prefix[i-1]+nums[i];
}
return prefix;
}
};Given an array of integers nums, you start with an initial positive value startValue.
In each iteration, you calculate the step by step sum of startValue plus elements in nums (from left to right).
Return the minimum positive value of startValue such that the step by step sum is never less than 1.
class Solution {
public:
int minStartValue(vector<int>& nums) {
int n = nums.size();
int ans = 0;
int prefix = 0;
for (int& num: nums) {
prefix += num;
ans = min(ans,prefix);
}
return -ans+1;
}
};You are given a 0-indexed array nums of n integers, and an integer k.
The k-radius average for a subarray of nums centered at some index i with the radius k is the average of all elements in nums between the indices i – k and i + k (inclusive). If there are less than k elements before or after the index i, then the k-radius average is -1.
Build and return an array avgs of length n where avgs[i] is the k-radius average for the subarray centered at index i.
The average of x elements is the sum of the x elements divided by x, using integer division. The integer division truncates toward zero, which means losing its fractional part.
For example, the average of four elements 2, 3, 1, and 5 is (2 + 3 + 1 + 5) / 4 = 11 / 4 = 2.75, which truncates to 2.
class Solution {
public:
vector<int> getAverages(vector<int>& nums, int k) {
int n = nums.size();
int d = 2*k+1;
vector<int> ans(n,-1);
if(n<d) {
return ans;
}
vector<long> prefix(n,nums[0]);
for(int i=1; i<n; i++) {
prefix[i] = prefix[i-1]+nums[i];
}
for(int i=k; i<n-k; i++) {
ans[i] = (prefix[i+k]-prefix[i-k]+nums[i-k])/d;
}
return ans;
}
};