class Solution { public int minSubarray(int[] nums, int p) { int n = nums.length; int m = 0; for (int x : nums) { m = (m + x) % p; //得到所需的元素和 } if(m == 0) { return 0; } int sum = 0, res = n; HashMapmap = new HashMap<>(); map.put(0, -1); for (int i = 0; i < n; i ++) { sum = (sum + nums[i]) % p; //得到的和 int q = (sum - m + p) % p; // if(map.containsKey(q)) { res = Math.min(res, i - map.get(q)); } map.put(sum, i); } return res == n ? -1 : res; // } }
2.974. 和可被 K 整除的子数组
class Solution { public int subarraysDivByK(int[] nums, int k) { HashMaprecord = new HashMap (); record.put(0,1); int sum = 0, ans = 0; for (int num : nums) { sum += num; int m = (sum % k + k) % k;//得到满足的数组 int same = record.getOrDefault(m, 0);//统计符合的数组的子数组... ans += same;//计数所得符合的数组 record.put(m, same + 1); } return ans; } }
3.剑指 Offer II 011. 0 和 1 个数相同的子数组
class Solution { public int findMaxLength(int[] nums) { int n = nums.length, sum = 0, res = 0; HashMapmap = new HashMap<>(); //和为0的时候下标为-1 map.put(0, -1); for(int i = 0; i < n; i++) { if(nums[i] == 0) { sum -= 1; }else { sum += 1; } if(map.containsKey(sum)) { res = Math.max(res, i - map.get(sum)); }else { map.put(sum, i); } } return res; } }
4.525. 连续数组
class Solution { public int findMaxLength(int[] nums) { int res = 0, sum = 0; for (int i = 0; i < nums.length; i++) { if(nums[i] == 0) { nums[i] = -1;//诺不存在的就返回-1 } } HashMapmap = new HashMap<>(); for (int i = 0; i < nums.length; i++) { sum += nums[i]; if(sum == 0 && i > res) {//找到的含有连续相同的0,1子数组 res = i + 1; } if(map.containsKey(sum)) { res = Math.max(i - map.get(sum), res);//返回连续相同0,1子数组的长度最大值 }else { map.put(sum, i); } } return res; } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)