560. Subarray Sum Equals K
class Solution {
public int subarraySum(int[] nums, int k) {
//커지면 앞에서 빼주고 작으면 계속 더하기~~~
//헐 대박...
if (nums.length <= 1) {
return (nums[0] == k) ? 1 : 0;
}
int start = 0;
int end = 1;
int sum = nums[start];
int total = 0;
while (start <= end) {
if (start == end) {
if (end >= nums.length) {
start++;
} else {
end++;
sum += nums[end];
}
} else if (sum == k) {
total++;
sum -= nums[start];
start++;
} else if (sum < k) {
sum += nums[end];
end++;
} else {
sum -= nums[start];
start++;
}
}
if (sum == k) {
total++;
}
return total;
}
}
처음에는 sliding window를 쓰려고 했읍니다..
근데 영 안돼서 생각을 해보니
마이나스..가 있다는점...^^
class Solution {
public int subarraySum(int[] nums, int k) {
int result = 0;
for (int i = 0; i < nums.length; i++) {
int sum = 0;
for (int j = i; j < nums.length; j++) {
sum += nums[j];
if (sum == k) {
result++;
}
}
}
return result;
}
}
Runtime: 1233 ms, faster than 17.54% of Java online submissions for Subarray Sum Equals K.
Memory Usage: 41 MB, less than 94.12% of Java online submissions for Subarray Sum Equals K.
그래서 이중포문이로 돌아왔읍니다~
말 그대로 일일이 뒤지는~ 방법~~
루션이
public class Solution {
public int subarraySum(int[] nums, int k) {
int count = 0, sum = 0;
HashMap < Integer, Integer > map = new HashMap < > ();
map.put(0, 1);
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (map.containsKey(sum - k))
count += map.get(sum - k);
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return count;
}
}
Runtime: 17 ms, faster than 95.77% of Java online submissions for Subarray Sum Equals K.
Memory Usage: 41.3 MB, less than 73.90% of Java online submissions for Subarray Sum Equals K.
제 사랑 쉬맵이로 이런거도 할 수 있군요...ㅎㅎ.......
알던 쉬맵이에다가 sum 값을 계속 넣어준다
Key, value ==> sum, frequency
sum 차이로 숫자를 찾는 느낌으루다가!
만약에 sum이 같은 게 나온다면 그 숫자가 될 수 있는 가짓수가 여러개라는 뜻이니 매번 나올때마다 frequency를 업데이트 해줌
그리고 쭉 가면서 만약에 총 sum - k가 전에 나온 적이 있다면
그 바로 앞까지만 더해서 k를 만들 수 있다는 뜻이니 그 숫자가 가능한 frequency 만큼 더해준다
루션이 천재같아요..
냅다외워!!!!
Author And Source
이 문제에 관하여(560. Subarray Sum Equals K), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jwade/560.-Subarray-Sum-Equals-K저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)