[线上课程题目]2015-01-05_YY线上课程题目及代码
01月5日, 2015 代码 knockgater 81次
01月5日, 2015 81次
给定一个无序数组arr，arr中元素可以是正数、负数和0，给定一个整数k，求arr所有子数组中，相加的和为k的最长子数组长度。
解法要求：时间复杂度O(N)，额外空间复杂度O(N)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
public static int getSumKMaxSubArrayLength(int[] arr, int k) { HashMap<Integer, Integer> valueFirstIndexMap = new HashMap<Integer, Integer>(); valueFirstIndexMap.put(0, -1); int len = 0; int sum = 0; for (int i = 0; i != arr.length; i++) { sum += arr[i]; if (valueFirstIndexMap.containsKey(sum - k)) { int minIndex = valueFirstIndexMap.get(sum - k); if (i - minIndex > len) { len = i - minIndex; } } if (!valueFirstIndexMap.containsKey(sum)) { valueFirstIndexMap.put(sum, i); } } return len; } |
给定一个数组arr，该数组无序且每个元素均为正数；在给定一个正数K，求arr所有子数组中所有元素相加和为K的最长子数组长度。
例如：
arr：1,2,1,1,1
K：3
结果返回3
解法要求：时间复杂度O(N)，额外空间复杂度O(1)
|
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 |
public static int getSumKMaxSubArrayLen(int[] arr, int k) { if (arr == null || arr.length == 0 || k < 0) { return 0; } int left = 0; int right = 0; int sum = arr[0]; int len = 0; while (right < arr.length) { if (sum == k) { if (right - left + 1 > len) { len = right - left + 1; } sum -= arr[left++]; } else if (sum < k) { right++; if (right == arr.length) { break; } sum += arr[right]; } else { sum -= arr[left++]; } } return len; } |
