leetcode 3 수의 합 mid
1641 단어 leetcode
우리 가 가장 생각 할 수 있 는 방법 은 n * n * log (n) 이지 만 n * n 의 방법 으로 해결 할 수 있 는 방법 이 있 는 지 알 수 있 습 니 다. 답 은 있 습 니 다.
우선 우 리 는 반드시 List 를 한 번 매 거 해 야 한다. 그러면 O (n) 의 복잡 도가 남 았 다. 우리 가 매 거 진 List, a + b + c = 0 을 생각 할 수 있다.
a + b = -c 매 거 진 - c 라 고 생각 합 니 다. 우 리 는 List 에서 a + b 를 찾 아야 합 니 다. List 의 수의 증가 성 으로 인해 우 리 는 자 에서 a + b 를 꺼 낼 수 있 습 니 다.
다른 왼쪽 점 은 0, 오른쪽 점 은 List. length - 1, List [0] + List [List. length - 1] - c 보다 크 면 오른쪽 점 을 왼쪽으로 기대 게 합 니 다. 이렇게 합 니 다.
a + b 가 줄 어 들 고 반대로 - c 보다 작 으 면 왼쪽 점 은 자 연 스 럽 게 오른쪽으로 이동 합 니 다.
class Solution {
static List> ret = new ArrayList>();
public static List> threeSum(int[] nums) {
ret.clear();
Arrays.sort(nums);
for(int i = 0; i < nums.length - 2; i++) {
int x = nums[i];
twoSum(nums, i + 1, -x);
while(i < nums.length - 2 && nums[i] == nums[i + 1]) i++;
}
return ret;
}
public static void twoSum(int[] nums, int start, int value) {
int l = start;
int r = nums.length-1;
while(l < r) {
if(nums[l] + nums[r] == value) {
List list = new ArrayList();
list.add(nums[start - 1]);
list.add(nums[l]);
list.add(nums[r]);
ret.add(list);
while(l < r && nums[l + 1] == nums[l]) l++;
while(l < r && nums[r - 1] == nums[r]) r--;
l++; r--;
}
else if(nums[l] + nums[r] > value){
r--;
}
else l++;
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
0부터 시작하는 LeetCode Day8 「1302. Deepest Leaves Sum」해외에서는 엔지니어의 면접에 있어서 코딩 테스트라고 하는 것이 행해지는 것 같고, 많은 경우, 특정의 함수나 클래스를 주제에 따라 실장한다고 하는 것이 메인이다. 빠른 이야기가 본고장에서도 행해지고 있는 것 같은 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
