关于我的 Leetcode 题目解答,代码前往 Github:https://github.com/chenxiangcyr/leetcode-answers
LeetCode题目:560. Subarray Sum Equals K
Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.
Example 1:
Input:nums = [1,1,1], k = 2
Output: 2
Note:
- The length of the array is in range [1, 20,000].
- The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].
以下代码的时间负责度为O(n^2)
:
class Solution {
public int subarraySum(int[] nums, int k) {
if(nums == null || nums.length == 0) return 0;
// sum[i]记录前i个元素的和
int[] sum = new int[nums.length];
sum[0] = nums[0];
for(int i = 1; i < nums.length; i++) {
sum[i] = sum[i - 1] + nums[i];
}
int count = 0;
// 遍历各个range
for(int i = 0; i < nums.length; i++) {
for(int j = i; j < nums.length; j++) {
if((sum[j] - (i == 0 ? 0 : sum[i - 1])) == k) {
count++;
}
}
}
return count;
}
}
以下代码的时间负责度为O(n)
:
class Solution {
public int subarraySum(int[] nums, int k) {
int count = 0;
int sum = 0;
// key: 累计和sum, value: 从idx = 0 开始有多少种方式可以累积到该sum
HashMap <Integer, Integer> map = new HashMap < > ();
map.put(0, 1);
for (int i = 0; i < nums.length; i++) {
sum = sum + nums[i];
if (map.containsKey(sum - k)) {
count = count + map.get(sum - k);
}
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return count;
}
}
LeetCode题目:325. Maximum Size Subarray Sum Equals k
Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn't one, return 0 instead.
Note:
The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range.
Example 1:
Given nums = [1, -1, 5, -2, 3], k = 3,
return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest)
Example 2:
Given nums = [-2, -1, 2, 1], k = 1,
return 2. (because the subarray [-1, 2] sums to 1 and is the longest)
Follow Up:
- Can you do it in O(n) time?
以下代码的时间负责度为O(n^2)
:
class Solution {
public int maxSubArrayLen(int[] nums, int k) {
if(nums == null || nums.length == 0) return 0;
// sum[i]记录前i个元素的和
int[] sum = new int[nums.length];
sum[0] = nums[0];
for(int i = 1; i < nums.length; i++) {
sum[i] = sum[i - 1] + nums[i];
}
int max = 0;
// 遍历各个range
for(int i = 0; i < nums.length; i++) {
for(int j = i; j < nums.length; j++) {
if((sum[j] - (i == 0 ? 0 : sum[i - 1])) == k) {
max = Math.max(max, j - i + 1);
}
}
}
return max;
}
}
以下代码的时间负责度为O(n)
:
class Solution {
public int maxSubArrayLen(int[] nums, int k) {
int max = 0;
int sum = 0;
// key: 累计和sum, value: 从idx = 0 开始第一次累积到该sum 的索引位置
// 为什么保存第一次的位置,因为是求 max size
HashMap <Integer, Integer> map = new HashMap < > ();
map.put(0, -1);
for (int i = 0; i < nums.length; i++) {
sum = sum + nums[i];
if (map.containsKey(sum - k)) {
max = Math.max(max, i - map.get(sum - k));
}
if (!map.containsKey(sum)) {
map.put(sum, i);
}
}
return max;
}
}
LeetCode题目:[53. Maximum Subarray]
(https://leetcode.com/problems/maximum-subarray/description/)
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.
以下代码的时间负责度为O(n^2)
:
class Solution {
public int maxSubArray(int[] nums) {
int max = Integer.MIN_VALUE;
for(int i = 0; i < nums.length; i++) {
int sum = 0;
for(int j = i; j < nums.length; j++) {
sum = sum + nums[j];
max = Math.max(max, sum);
}
}
return max;
}
}
以下代码的时间负责度为O(n)
:
class Solution {
public int maxSubArray(int[] nums) {
// dp[i] means the maximum subarray ending with A[i]
int[] dp = new int[nums.length];
// init
dp[0] = nums[0];
int max = dp[0];
for(int i = 1; i < nums.length; i++){
dp[i] = nums[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
max = Math.max(max, dp[i]);
}
return max;
}
}
网友评论