제3 장, 조건 을 만족 시 키 는 두 개 이상 의 수 와 그 확장 을 찾는다.

제1 절, 조건 을 만족 시 키 는 두 가지 수 를 찾는다.
제목: 하나의 배열 과 하나의 숫자 를 입력 하고 배열 에서 두 개의 수 를 찾 아 입력 한 숫자 와 맞 게 합 니 다.요구 시간 복잡 도 는 O (n) 이다.만약 여러 쌍 의 숫자 와 입력 한 숫자 가 있다 면, 임의의 한 쌍 을 출력 하면 된다.예 를 들 어 배열 1, 2, 4, 7, 11, 15 와 숫자 15 를 입력 하 십시오.4 + 11 = 15 이기 때문에 4 와 11 을 출력 합 니 다.분석:

배열 에서 두 개의 수 를 임의로 선택 하여 그들의 숫자 와 입력 여 부 를 판단 한다.이 복잡 도 는 O (N ^ 2) 입 니 다.우 리 는 효율 이 더 높 은 해법 을 찾 아야 한 다 는 것 이 분명 하 다.

문 제 는 모든 a [i] 에 대해 sum - a [i] 도 원시 서열 에 있 는 지, 매번 찾 아야 할 시간 이 O (N) 인지 판단 하 는 것 과 같다. 이렇게 되면 최종 적 으로 두 개의 수 를 찾 으 려 면 O (N ^ 2) 의 복잡 도가 필요 하 다.그러면 어떻게 판단 을 찾 는 속 도 를 높 입 니까?참, 2 분 검색 은 원래 O (N) 의 검색 시간 을 O (logN) 로 높 여야 합 니 다. 그러면 N 개 a [i] 에 대해 서 는 해당 하 는 sum - a [i] 가 원시 서열 에서 전체 시간 복잡 도 는 O (N * logN) 로 떨 어 졌 고 공간 복잡 도 는 O (1) 로 떨 어 졌 는 지 찾 는 데 시간 이 걸 립 니 다.(질서 가 있 으 면 직접 2 점 O (N * logN), 무질서 하면 먼저 정렬 한 후 2 점, 복잡 도 역시 O (N * logN + N * logN) = O (N * logN), 공간 총 O (1) 이다.

더 좋 은 방법 이 있 습 니까?우 리 는 상기 사고 2 의 사상 에 따라 a [i] 서열 에서 a [i] + a [k] = sum 이 라면 sum - a [i] (a [k]) 도 반드시 서열 에 있 을 것 이다. 예 를 들 어 다음 과 같다.
원시 서열: 1, 2, 4, 7, 11, 15     입력 숫자 15 로 각 수 를 줄 이 고 대응 하 는 순 서 는 다음 과 같 습 니 다.
대응 서열: 14, 13, 11, 8, 4, 0     
첫 번 째 배열 은 하나의 포인터 i 로 배열 의 가장 왼쪽 끝 에서 오른쪽으로 스 캔 하고 두 번 째 배열 은 하나의 포인터 j 로 배열 의 가장 오른쪽 끝 에서 왼쪽으로 스 캔 합 니 다. 만약 에 아래 에 위 와 같은 숫자 가 나타 나 면 a [* i] = a [* j] 를 찾 아 냈 습 니 다.위 와 같이 i, j 는 최종 적 으로 첫 번 째, 두 번 째 서열 에서 같은 수 4 와 11 을 찾 았 기 때문에 조건 에 부합 되 는 두 개의 수, 즉 4 + 11 = 15 이다.어떻게 양 끝 을 동시에 찾 으 면 시간 복잡 도가 순식간에 O (N) 로 줄 어 들 지만 O (N) 의 공간 이 두 번 째 배열 (이 배열 은 질서 있 는 배열) 을 저장 해 야 합 니 다 (O (N).복잡 도, 첫 번 째 배열 은 하나의 포인터 i 로 배열 의 맨 왼쪽 끝 에서 오른쪽으로 스 캔 합 니 다. 두 번 째 배열 은 하나의 포인터 j 로 배열 의 맨 오른쪽 끝 에서 왼쪽으로 스 캔 합 니 다. 먼저 i 는 요소 1, j 는 요소 0 을 가리 키 고 누가 원 소 를 가리 키 며 누가 먼저 이동 합 니까? 1 (i) > 0 (j)그래서 i 는 움 직 이지 않 고 j 는 왼쪽으로 이동 합 니 다. 그리고 j 는 요소 4 로 이동 하면 요소 1 보다 큰 것 을 발견 하고 j 이동 을 멈 추고 i 가 4 를 가리 킬 때 까지 이동 합 니 다. 이때 i 가 가리 키 는 요 소 는 j 가 가리 키 는 요소 와 같 기 때문에 4 는 조건 을 만족 시 키 는 첫 번 째 숫자 라 고 판단 한 다음 에 i, j 를 동시에 이동 하여 경계 에 도달 할 때 까지 판단 합 니 다).

물론 hash 표를 구성 할 수 있 습 니 다. 프로 그래 밍 의 아름다움 에서 말 한 것 처럼 하나의 숫자 를 정 하고 hash 맵 에 따라 다른 숫자 도 배열 에 있 는 지 찾 을 수 있 습 니 다. O (1) 의 시간 만 사용 하면 전체적인 알고리즘 은 상기 사고 3 과 마찬가지 로 O (N) 로 내 려 갈 수 있 습 니 다. 그러나 결함 이 있 습 니 다. 바로 구조 hash 가 O (N) 의 공간 을 추가 로 증가 하 는 것 입 니 다.이 점 은 상술 한 사고 와 같다.그러나 공간 이 시간 을 바 꾸 는 것 은 시간 요구 가 비교적 엄격 한 상황 에서 좋 은 방법 이다
만약 에 배열 이 무질서 하 다 면 먼저 정렬 (n * logn) 한 다음 에 두 개의 포인터 i, j 로 각각 배열 의 앞 뒤 양쪽 을 가리 키 고 i = 0, j = n - 1, 그 다음 에 i +, j - 를 가리 키 며 a [i] + a [j]? =sum, 만약 어느 순간 a [i] + a [j] > sum 이 라면 sum 의 값 을 줄 일 방법 을 생각해 야 합 니 다. 그래서 지금 i 는 움 직 이지 않 습 니 다. j -, 만약 어느 순간 a [i] + a [j] < sum 이 라면 sum 의 값 을 늘 릴 방법 을 생각해 야 합 니 다. 그래서 지금 i +, j 는 움 직 이지 않 습 니 다.따라서 배열 이 무질서 할 때 시간 복잡 도 는 최종 적 으로 O (n * logn + n) = O (n * logn) 이다. 만약 에 원래 배열 이 질서 가 있 으 면 사전 정렬 이 필요 없고 직접 O (n) 로 해결 할 필요 가 없 으 며 공간 복잡 도 는 O (1) 이다. 이 사 고 는 상기 모든 사고 에 비해 개선 되 었 다.(질서 가 있 으 면 두 개의 포인터 양 끝 을 직접 스 캔 하고 시간 O (N), 순서 가 없 으 면 먼저 정렬 한 후 양 끝 을 스 캔 하고 시간 O (N * logN + N) = O (N * logN), 공간 은 항상 O (1) 이다.(상기 사고방식 2 에 비해 정렬 후의 시간 비용 은 이전의 2 분 의 n * logn 에서 스캐닝 의 O (N) 로 낮 아 졌 다.
요약:
원래 의 서열 이 질서 가 있 든 무질서 하 든 이런 문 제 를 해결 하 는 데 다음 과 같은 세 가지 방법 이 있다. 1, 2 분 찾기 (순서 가 없 으 면 먼저 정렬 한 다음 에 2 분), 시간 복잡 도 는 모두 O (n * logn) 이 고 공간 복잡 도 는 O (1) 이다.2. X - S [i] 스 캔 하기  하나의 배열 이나 구조 hash 표 에 투사 되 고 시간 복잡 도 는 O (n) 이 며 공간 복잡 도 는 O (n) 이다.3. 두 개의 포인터 양 끝 스 캔 (순서 가 없 으 면 먼저 정렬 한 다음 스 캔), 시간 복잡 도 는 마지막 으로 질서 O (n), 무질서 O (n * logn + n) = O (n * logn), 공간 복잡 도 는 모두 O (1) 이다
따라서 시간 O (N), 공간 O (1) 의 목 표를 달성 하려 면 원래 배열 이 질서 있 는 (포인터 스 캔 법) 이 아니면 배열 이 순서 가 없 으 면 먼저 정렬 할 수 밖 에 없다. 그 다음 에 포인터 스 캔 법 이나 2 분 (시간 n * logn, 공간 O (1) 또는 맵 또는 hash (시간 O (n), 공간 O (n)).시간 이나 공간 은 하 나 를 희생 하고 스스로 저울질 해 야 한다
4. 567917. 종합 적 으로 배열 이 질서 가 있 는 상황 에서 두 개의 포인터 양 끝 스 캔 법 을 우선 고려 하여 가장 좋 은 시 (O (N), 공 (O (1) 효 과 를 얻 도록 한다.그렇지 않 으 면 정렬 을 하려 면 시간 복잡 도가 가장 빠 르 면 당연히 N * logN 에 만 도달 할 수 있 고 공간 O (1) 는 문제없다

제2 절, 조건 을 만족 시 키 는 여러 개 수 를 찾는다.
프로 그래 밍 설명: 두 개의 정수 n 과 m 를 입력 하고 수열 1, 2, 3.해법

#include<list>
#include<iostream>
using namespace std;

list<int>list1;
void find_factor(int sum, int n) 
{
    //     
    if(n <= 0 || sum <= 0)
        return;
    
    //        
    if(sum == n)
    {
        //   list
        list1.reverse();
        for(list<int>::iterator iter = list1.begin(); iter != list1.end(); iter++)
            cout << *iter << " + ";
        cout << n << endl;
        list1.reverse();    
    }
    
	list1.push_front(n);      //   01    
	find_factor(sum-n, n-1);   // n，n-1    sum-n
	list1.pop_front();
	find_factor(sum, n-1);     //  n，n-1    sum	
}

int main()
{
    int sum, n;
    cout << "            sum:" << endl;
    cin >> sum;
    cout << "      1.....n      n：" << endl;
    cin >> n;
    cout << "       ，  ：" << endl;
    find_factor(sum,n);
    return 0;
}

해법 2. 이 문 제 는 부분 집합 과 문제 (가방 문제) 에 속한다.이 프로그램 은 역 추적 법 + 가지치기 X 배열 을 사용 하여 해 벡터, t = ＞ (1,.., k - 1) Wi * Xi, r = ＞ (k,.., n) Wi 약 t + Wk + W (k + 1) < = M, 그러면 Xk = true, 왼쪽 아들 (X1, X2,.., X (k - 1), 1) 로 재 귀 합 니 다.그렇지 않 으 면 가 지 를 잘라 라.만약 t + r - Wk > = M & & t + W (k + 1) < = M 이 라면 Xk = 0 을 두 고 오른쪽 아들 (X1, X2,.., X (k - 1), 0) 에 게 귀속 한다.그렇지 않 으 면 가 지 를 잘라 라.
이 문제 에서 W 배열 은 (1, 2,..., n) 이 므 로 직접 k 로 WK 값 을 대체 합 니 다.코드 는 다음 과 같 습 니 다:

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

/** 
 *   t， r，   Wk
 */
void sumofsub(int t, int k ,int r, int& M, bool& flag, bool* X)
{
    X[k] = true;   //   k  
    if (t + k == M) //        M，          ，   
    {
        flag = true;
        for (int i = 1; i <= k; ++i)
        {
            if (X[i] == 1)
            {
                printf("%d ", i);
            }
        }
        printf("
");
    }
    else
    {   //   k+1      ，      
        if (t + k + (k+1) <= M)
        {
            sumofsub(t + k, k + 1, r - k, M, flag, X);
        }
        //     k  ，  k+1      ，      
        if ((t + r - k >= M) && (t + (k+1) <= M))
        {
            X[k] = false;
            sumofsub(t, k + 1, r - k, M, flag, X);
        }
    }
}

void search(int& N, int& M)
{
    //       
    bool* X = (bool*)malloc(sizeof(bool) * (N+1));
    memset(X, false, sizeof(bool) * (N+1));
    int sum = (N + 1) * N * 0.5f;
    if (1 > M || sum < M) //         
    {
        printf("not found/n");
        return;
    }
    bool f = false;
    sumofsub(0, 1, sum, M, f, X);
    if (!f)
    {
        printf("not found/n");
    }
    free(X);
}

int main()
{
    int N, M;
    printf("     N M/n");
    scanf("%d%d", &N, &M);
    search(N, M);
	return 0;
}

제3 절, 조건 을 만족 시 키 는 수의 확장 문 제 를 찾는다.
1. 한 열 에서 가능 한 한 적은 수 를 걸 러 내 서 왼쪽 에서 오른쪽으로 보면 이 수 는 작은 것 에서 큰 것, 작은 것 (이해 하지 못 함) 이다.
분석: 양 끝 LIS 문 제 는 DP 의 사상 으로 풀 수 있 습 니 다. 목표 계획 함수 max {b [i] + c [i] - 1}, 그 중에서 b [i] 는 왼쪽 에서 오른쪽, 0 ~ i 개 수 사이 에 증가 하 는 숫자 개 수 를 만족 시 킵 니 다.c [i] 오른쪽 에서 왼쪽으로 n - 1 ~ i 개 수 사이 에 증가 하 는 숫자 개 수 를 만족 시 키 기 위해 서 입 니 다.마지막 결 과 는 n - max + 1 입 니 다.그 중에서 DP 는 하나의 inc [] 배열 을 유지 할 수 있 습 니 다. inc [i] 는 어 릴 때 부터 큰 i 까지 의 숫자 를 표시 하고 b [i] c [i] 를 계산 할 때 2 점 으로 inc [] 에서 구간 inc [0] ~ inc [i - 1] 에서 a [i] 보다 작은 요소 개수 (low) 를 찾 을 수 있 습 니 다.2.2 두 개의 서열 a, b 가 있 는데 크기 는 모두 n 이 고 서열 요소 의 값 은 임 의 정수 이 며 순서 가 없다.요구: a, b 의 요 소 를 교환 하여 [서열 a 요소 의 합] 과 [서열 b 요소 의 합] 간 의 차 이 를 최소 화 합 니 다.예 를 들 면:  var a=[100,99,98,1,2, 3];var b=[1, 2, 3, 4,5,40];(이해 못 함)