[LeetCode] 209. 최소 크기 Subarray Sum 문제 풀이 보고서 (Python & C + +)
제목 주소:https://leetcode.com/problems/minimum-size-subarray-sum/description/
제목 설명:
Given an array of
n
positive integers and a positive integer s, find the minimal length of a contiguous
subarray of which the sum ≥ s
. If there isn’t one, return 0 instead. Example:
Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.
Follow up:
제목 의 대의
한 배열 에서 가장 짧 고 연속 적 인 하위 배열 을 찾 아 라. 이 하위 배열 의 합 요 > = s.
문제 풀이 방법
충 취 법
공교롭게도 오늘 이라는 책 에서 이 문 제 를 보 았 는데 해법 을 벌레 취 법 이 라 고 하 는데 사실은 두 바늘 이다.사실 연속 서브 배열 이 일정한 조건 을 만족 시 키 는 것 을 본 많은 사람들 이 두 개의 지침 을 사용 했다. 예 를 들 어 713. Subarray Product Less Than K.
이 문 제 는 최소 값 을 요구 하기 때문에 결 과 는 inf 로 초기 화 되 었 습 니 다. 오른쪽 지침 을 이동 할 때마다 조건 을 만족 시 킬 때 결 과 를 업데이트 하고 왼쪽 지침 을 이동 하 며 왼쪽 숫자 를 삭제 하 는 것 을 기억 합 니 다.여기 서 화 해 를 구 하 는 구간 은 좌우 모두 폐 구간 이다.
시간 복잡 도 는 O (N) 이 고 공간 복잡 도 는 O (1) 이다.
class Solution:
def minSubArrayLen(self, s, nums):
"""
:type s: int
:type nums: List[int]
:rtype: int
"""
N = len(nums)
l, r = 0, 0
csum = 0
res = float('inf')
while r < N:
csum += nums[r]
while csum >= s:
res = min(res, r - l + 1)
csum -= nums[l]
l += 1
r += 1
return res if res != float('inf') else 0
2 솔 을 칠 할 때 C + + 를 사 용 했 습 니 다. 저 는 벌레 취 법 을 선 택 했 지만 벌레 취 법 에 대해 100% 자신 이 없습니다. 많은 문제 의 벌레 취 법 은 이 해 를 빠 뜨 릴 수 있 기 때문에 쉽게 발견 하지 못 할 것 입 니 다.다행히 이 문 제 는 정수 만 있어 좌우 지침 을 움 직 이 는 규칙 을 쉽게 찾 을 수 있 기 때문에 벌레 를 잡 는 방법 은 문제 가 없다.
나 는 두 개의 포인터 left 와 right 를 정 의 했 고 sum = [left... right) 의 합 을 정 의 했 습 니 다. 그 중에서 구간 은 왼쪽 닫 고 오른쪽 열 립 니 다. 그러면 right 종료 조건 은 right < = N 이 고 문제 의 요 구 를 만족 시 키 는 구간 의 길 이 는 right - left 입 니 다. 이 를 알 게 되면 코드 를 쉽게 쓸 수 있 습 니 다.
C + + 코드 는 다음 과 같 습 니 다.
class Solution {
public:
// O(N) using two pointer
int minSubArrayLen(int s, vector<int>& nums) {
const int N = nums.size();
if (N == 0) return 0;
int left = 0, right = 0;
// sum = sum[left, right)
long long sum = 0;
int res = INT_MAX;
while (right <= N) {
if (sum >= s) {
res = min(res, right - left);
sum -= nums[left++];
} else {
sum += nums[right++];
}
}
return res == INT_MAX ? 0 : res;
}
};
이분 찾기
이 문 제 는 follow up 이 있 습 니 다. 우 리 는 o (NLogN) 의 시간 복잡 도 로 해결 하 라 고 합 니 다. 분명히 우리 의 2 분 을 고찰 하고 있 습 니 다.
생각 은 분명 하 다. 각 위치 에 대해 배열 의 누적 과 누적 과 모든 위치 에 대해 sums [i] - pos 의 위치 가 sums 중의 어디 에 있 는 지 찾 아 보 자. 그러면 한 구간 을 얻 을 수 있다. 이 구간 의 누적 과 s 보다 작 지 않 은 것 이 바로 제목 이다.
이 문 제 는 제 가 쓴 2 점 은 첫 번 째 숫자 보다 작 지 않 은 위 치 를 찾 는 것 입 니 다. 즉, lower bound 입 니 다. 그러면 찾 으 려 는 target 이 sums 에 없 을 때 돌아 오 는 결 과 는 오른쪽 에 있 는 첫 번 째 숫자 입 니 다. 따라서 판단 을 해 야 합 니 다. 찾 으 면 구간 길이 가 i - pos 입 니 다. 그렇지 않 으 면 구간 길이 가 + 1 이 어야 합 니 다.
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
const int N = nums.size();
vector<int> sums;
sums.push_back(0);
for (int i = 0; i < N; ++i) {
sums.push_back(nums[i] + sums.back());
}
int res = INT_MAX;
for (int i = 1; i <= N; ++i) {
int target = sums[i] - s;
if (target < 0) continue;
auto pos = binary_search(sums, target);
if (pos > N) continue;
if (sums[i] - sums[pos] == s)
res = min(res, i - pos);
else if (sums[i] - sums[pos] < s)
res = min(res, i - pos + 1);
}
return res == INT_MAX ? 0 : res;
}
int binary_search(vector<int>& sums, int target) {
const int N = sums.size();
// [l, r)
int l = 0, r = N;
while (l < r) {
int mid = l + (r - l) / 2;
if (sums[mid] >= target) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
};
참고 자료:
날짜.
2018 년 10 월 15 일 - 좋 은 월요일 에 어떻게 미세 먼지 가 발생 할 수 있 습 니까? 2019 년 1 월 11 일 - 빼 빼 로 데 이?
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.