LeetCode 16_3Sum Closest

오늘 시간 을 좀 내 서 닦 아 보 겠 습 니 다.
이것 은 16 번 문제 입 니 다. 이 연속 몇 문제 의 유형 은 모두 비슷 합 니 다. 모두 배열 에 대한 조합 을 요구 한 다음 에 그 중에서 특정한 조건 에 부합 되 는 조합 을 찾 아야 합 니 다. 이런 문 제 는 비교적 큰 문제 형 이 라 고 할 수 있 습 니 다. 많은 문제 들 이 결국 이런 문제 로 바 뀌 었 습 니 다. 첫 번 째 문제 에서 두 개의 수 를 찾 아 주어진 값 으로 하고 뒤에 있 는 가장 큰 물탱크 의 문제 도 있 습 니 다.위 에 세 개의 수 를 구 하 는 것 과 특정 값 을 구 하 는 모든 조합.이 문제 들 은 모두 이렇다. 앞의 문 제 를 통 해 우 리 는 일반적인 '처리 방식', 즉 먼저 정렬 한 다음 에 처리 하 는 방법 을 알 게 되 었 다.물론 모든 문 제 는 각 문제 의 특징 이 있 기 때문에 구체 적 인 세부 사항 은 스스로 처리 해 야 한다.더 이상 말 하지 않 겠 습 니 다. 오늘 이 문 제 를 보 겠 습 니 다.
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

오늘 이 문 제 는 배열 에서 세 개의 숫자 를 합 친 것 으로 주어진 숫자 와 가장 가깝다.
우선, 이러한 문제 의 큰 방침 을 파악 하려 면 먼저 정렬 이 쓸모 가 있 는 지 살 펴 봐 야 한다. 왜냐하면 만력 법의 복잡 도 는 O (n ^ 3) 이기 때문이다. 이런 알고리즘 은 80% 는 개선 여지 가 존재 하고 개선 여지 의 80% 는 먼저 정렬 한 다음 에 찾 는 것 이다.우 리 는 이전 문제 와 가 까 운 사 고 를 이용 하여 먼저 하 나 를 확정 한 다음 에 나머지 를 양 끝 검색 을 한다. 양 끝 검색 이 가능 한 지 여 부 는 양 끝 점 데이터 에 대한 판단 을 통 해 이동 단 과 그 이동 방향 을 결정 할 수 있 는 지 에 달 려 있다.현재 이 문 제 는 '작 으 면 크게, 작 으 면 작 게' 준칙 으로 이동 단 과 이동 방향 을 판단 할 수 있다.
그 다음 에 정렬 의 유효성 과 이동 전략 을 확정 했다. 기본적으로 이 문 제 는 이미 해결 되 었 다. 나머지 는 이동 과정 에서 어떤 판단 을 해 야 하 는 지, 그리고 어떻게 값 을 부여 해 야 하 는 지 를 확정 하 는 것 이다. 이 문 제 는 요구 와 가장 가 까 운 세 개의 수 이기 때문에 가장 가 까 운 세 개의 수 를 기록 한 다음 에 이 값 을 계속 스 캔 하여 업데이트 해 야 한다.그리고 주의해 야 할 것 은 건 너 뛸 수 있 는 스 캔 항목 을 주의 하 는 것 입 니 다. 중복 되 는 숫자 는 건 너 뛸 수 있 습 니까? 이번 양 끝 스 캔 을 미리 끝 낼 수 있 습 니까?이 문제 에 대해 중복 숫자 는 건 너 뛸 수 있 는 액 이 고 양 끝 스 캔 은 미리 중지 할 수 없다. 즉, 전체 배열 을 다 써 야 하 는 이 유 는 여러분 이 분석 하면 된다. 쉽게 말 하면 현재 의 양 끝 값 을 판단 함으로써 중간 에 더 좋 은 조합 이 있 는 지 확인 할 수 없다 는 것 이다.
마지막 으로 당연히 코드 입 니 다. 여 기 는 본인 의 코드 를 사용 하 세 요. 큰 신의 것 도 비슷 하기 때문에 알고리즘 은 똑 같 습 니 다.

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
		//      
		int len=nums.size();
		//     
		sort(nums.begin(),nums.end());
		//      
		int result=nums[0]+nums[1]+nums[len-1];
		//int result;
		int lef=0,rig=0;
		for(int i=0;i<len-2;++i)
		{
			lef=i+1;rig=len-1;
			//cur_result=nums[i]+nums[lef]+nums[rig];
			if(i!=0 && nums[i]==nums[i-1])continue;//      
			while(lef<rig)
			{
				if(lef!=i+1&&nums[lef]==nums[lef-1]){lef++;continue;}//      
				if(rig!=len-1&&nums[rig]==nums[rig+1]){rig--;continue;}//      
				if(nums[i]+nums[lef]+nums[rig]==target)
					return target;
				else if(nums[i]+nums[lef]+nums[rig]<target)//  target
				{
					result = abs(result-target)>abs(nums[i]+nums[lef]+nums[rig]-target)?
								nums[i]+nums[lef]+nums[rig] : result;
					lef++;
				}
				else if(nums[i]+nums[lef]+nums[rig]>target)//  target
				{
					result = abs(result-target)>abs(nums[i]+nums[lef]+nums[rig]-target)?
								nums[i]+nums[lef]+nums[rig] : result;
					rig--;
				}
			}
		}
		return result;
	}
};

이 코드 의 운행 시간 은 16ms 입 니 다. leetcode 에는 아직도 12ms 의 코드 가 많 습 니 다. 좀 더 세련 되 게 보 세 요. 여러분 이 가서 보 세 요. 저 는 붙 이지 않 겠 습 니 다. 그리고 코드 는 8ms 입 니 다. 이것 은 비교적 강력 합 니 다. 더욱 효과 적 인 알고리즘 을 사 용 했 습 니까? 아니면 일부 인 코딩 방법 만 개선 한 것 입 니까?안 타 깝 게 도 대응 하 는 코드 를 찾 지 못 하면 우 리 는 알 수 없다. 만약 에 더 좋 은 알고리즘 을 이용 했다 고 가정 하면 이 알고리즘 의 시간 복잡 도 는 O (nlogn) 일 가능성 이 높다. 그 문제 에 O (nlogn) 의 해법 이 존재 하 는 지, 존재 한다 면 왜 존재 하 는 지, 존재 하지 않 는 것 이 무엇 인지, 우 리 는 이 문 제 를 빌려 이런 문 제 를 요약 한다.
우선 O (n ^ 2) 부터 O (n) 까지.이것 은 흔히 말 하 는 것 이다. 즉, 정렬 을 통 해 시간의 복잡 도 를 낮 출 수 있 는 상황 이다. 앞에서 말 했 듯 이 이런 문제 의 특징 은 정렬 한 후에 두 조합의 문 제 를 양 끝 검색 의 문제 로 간략화 할 수 있 고 양 끝 검색 을 할 수 있 는 앞에서 도 말 했다. 즉, 양 끝 데이터 에 대한 판단 을 통 해 이동 단 과 그 이동 방향 을 결정 할 수 있 는 지 하 는 것 이다.이런 특성 을 복합 한 문 제 는 모두 단조 로 운 비 감 (또는 비 증) 의 성질 을 가지 고 있다. 예 를 들 어 첫 번 째 문제 안의 두 숫자의 합 과 단조 로 운 개념 이 므 로 우 리 는 이 를 통 해 이동 방향 을 확정 할 수 있다.일부 순환 하 는 것 은 이렇게 할 수 없다. 비교 해 보면 나머지 연산 을 하 는 것 은 데이터 에 대해 정렬 을 하 더 라 도 그 쪽으로 이동 해 야 한 다 는 것 을 확정 할 수 없다.한 마디 로 하면 먼저 정렬 하고 검색 하 는 사고방식 은 O (n ^ 2) 의 알고리즘 을 O (n) 로 낮 추 는 것 이다.
그 다음 에 2 분 에 찾 아 보 세 요.2 분 검색 은 O (logn) 를 만 드 는 데 가장 많이 사용 되 는 알고리즘 이기 때문에 2 분 검색 을 본 문제 에 활용 하면 O (nlogn) 알고리즘 이 생 길 수 있 습 니 다.과연 가능 할 까? 우 리 는 먼저 2 분 검색 이 어떤 성질 을 가지 고 있 는 지 분석 해 보 자. 2 분 검색 을 할 수 있 는 조건 은 먼저 정렬 배열 이 고 그 다음 에 2 분 검색 의 유효성 이다. 언제 2 분 검색 이 효과 적 일 까?그것 은 바로 숫자 가 빠 지지 않 는 다 는 것 이다. 즉, 검색 결과 가 정확 하 다 는 것 이다. 일반적인 검색 은 모두 정확 한 수 를 찾 는 것 이다. 그러면 분명히 숫자 가 빠 지지 않 을 것 이다.그러나 본 문 제 는 우리 가 전체 2 단 으로 찾 고 중간 에 2 점 으로 찾 는 알고리즘 을 사용 하면 원 하 는 대로 O (nlogn) 의 알고리즘 을 얻 을 수 있 습 니까?우선 2 분 검색 의 유효성 을 확인 하고 우 리 는 어떤 수 를 찾 아야 합 니까?우리 가 찾 아야 할 것 은 가장 가 까 운 수 입 니 다. 2 점 에서 가장 가 까 운 수 를 찾 을 수 있 습 니까?답 은 긍정 적 이다. 우리 의 검색 은 요구 하 는 결 과 를 찾 을 수 있다. 즉, 찾 아야 할 수 를 찾 았 거나 왼쪽 과 오른쪽 수 를 찾 을 수 있다. 그러면 가장 가 까 운 수 를 찾 을 수 있다.그 다음 에 가장 가 까 운 수 를 찾 으 면 양쪽 검색 의 이동 방향 을 정할 수 있 습 니까?이것 은 안 됩 니 다. 만약 이번에 찾 은 것 과 target 보다 작다 면 왼쪽 끝 점 을 오른쪽으로 이동 해 야 한 다 는 것 을 설명 할 수 있 습 니까?분명 아 닙 니 다. 중간 상황 은 모 르 기 때 문 입 니 다. 오른쪽 을 왼쪽으로 옮 겨 2 분 에 찾 으 면 target 의 수 를 찾 을 수 있 습 니 다. 이런 상황 은 배제 할 수 없습니다. 즉, 맨 왼쪽 의 그 수 를 정렬 할 수 없습니다.이렇게 양쪽 에서 검색 하 자마자 효력 을 잃 었 다. 즉, 이런 방법 은 불가능 하 다 는 것 이다.
마지막 으로 한 마디 를 정리 하면 먼저 순 서 를 매 기 는 것 은 양 끝 검색 을 실현 하기 위해 서 이다. 양 끝 검색 과 2 점 검색 을 결합 하면 더욱 좋 은 효과 가 있 을 수 있다. 구체 적 인 문 제 는 구체 적 으로 분석 하고 방향 을 분석 하 는 것 이 바로 이런 것 이다.
곧 추석 인 데 추석 잘 보 내세 요!지 켜 지 는 모든 꿈 이 이 루어 지 길 바 랍 니 다!