나는 다음 코드의 논리를 이해하려고 노력하고 있지만 논리를 지원하는 수학이 현재 나에게 완전히 명확하지 않기 때문에 코드의 두 부분에 대해 부분적으로 명확하지 않습니다.
혼란 1 : 배열의 합을 찾기 시작하기 전에지도에 count = 1 인 0을 넣는 이유를 이해하지 못합니다. 어떻게 도움이 되나요?
혼란 2 :map.put(sum, map.getOrDefault(sum)+1) if () 조건 이후 로 이동 하면 올바른 솔루션을 얻습니다. 그러나 아래 코드와 같이 위치에 넣으면 잘못된 결과가 나타납니다. 문제는 카운트를 찾기 위해 맵에서 sum-k 값을 검색 할 때이 위치가 중요한 이유입니다.
public int subarraySum(int[] nums, int k) {
HashMap<Integer,Integer> prefixSumMap = new HashMap<>();
prefixSumMap.put(0, 1); // CONFUSION 1
int sum = 0;
int count = 0;
for(int i=0; i<nums.length; i++) {
sum += nums[i];
prefixSumMap.put(sum, prefixSumMap.getOrDefault(sum, 0)+1); //CONFUSION 2
if(prefixSumMap.containsKey(sum - k)) {
count += prefixSumMap.get(sum - k);
}
}
return count;
}
이것이 흥미로울 것입니다. 정수 오버플로로 인해 음수가 발생하지 않도록 long을 사용하는 방법을 수정했습니다.
이 두 방법 모두 양수에 대해 잘 작동합니다. 첫 번째 방법이 훨씬 간단하지만 둘 다 테스트 배열에 대해 동일한 개수를 반환합니다.
public static void main(String[] args) {
Random r = new Random();
long[] vals = r.longs(10_000_000, 1, 1000).toArray();
long k = 29329;
System.out.println(positiveValues(vals, k));
System.out.println(anyValues(vals, k));
public static int positiveValues(long[] array, long k) {
Map<Long,Long> map = new HashMap<>(Map.of(0L,1L));
int count = 0;
long sum = 0;
for (long v : array) {
sum += v;
map.put(sum,1L);
if (map.containsKey(sum-k)) {
count++;
}
}
return count;
}
public static int anyValues(long[] nums, long k) {
HashMap<Long,Long> prefixSumMap = new HashMap<>();
prefixSumMap.put(0L, 1L);
long sum = 0;
int count = 0;
for(int i=0; i<nums.length; i++) {
sum += nums[i];
prefixSumMap.put(sum, prefixSumMap.getOrDefault(sum, 0L)+1L);
if(prefixSumMap.containsKey(sum - k)) {
count += prefixSumMap.get(sum - k);
}
}
return count;
}
또한 성명
long v = prefixSumMap.getOrDefault(sum, 0L) + 1L;
양수 배열의 경우 항상 1을 반환합니다. 이는 이전 합계가 양수 값에 대해서만 다시 발생할 수 없기 때문입니다.
그 진술과 count맵에서 값을 취하여 계산 하는 것은 배열이 양수와 음수를 모두 포함하도록 허용하는 것입니다. 그리고 그것은 참 -k이고 모든 양의 값입니다.
다음 입력의 경우 :
long[] vals = {1,2,3,-3,0,3};
합계가 3 인 부분 배열은 다음과 같습니다.
(1+2), (3), (1+2+3-3), (1+2+3-3+0), (3-3+0+3), (0+3), (3)
음수를 추가하면 이전 합계가 나올 수 있으므로이를 고려해야합니다. 양수 값에 대한 솔루션은이를 수행하지 않습니다.
이것은 모든 음수 값에도 적용됩니다. 경우 k긍정적, no모든 금액은 음수가 될 것이기 때문에 부분 배열을 찾을 수 있습니다. k음수 이면 하나 이상의 하위 배열을 may찾을 수 있습니다.
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다