两数之和

题目

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数. 假设每个输入只对应一种答案，且相同的元素不能被重复利用
示例:

给定nums = [2, 7, 11, 15]，target = 9,因为nums[0] + nums[1] = 2 + 7 = 9，
所以返回[0, 1]

分析

将数组元素按照奇偶分为两个数组A，B

• 如果target是偶数，则数组中满足条件的两个元素必定都在A中或者都在B中
• 如果target是奇数，则数组中满足条件的两个元素必定一个在A中，另一个在B中

排序并寻找目标元素

• 分别对数组A，B的元素进行排序
• 设计目标元素查找算法
• 在有序数组A，B中查找目标元素

数组元素排序

堆排序 （以建立大根堆为例）:

• 性质

  • 堆中的元素序号按照完全二叉树的顺序排列
  • 堆中任何一个非叶子节点的关键字均不小于其孩子节点

• 建立大根堆
  以整型数组为例a[]={16,7,3,20,17,8}：
  构建一颗完全二叉树，让数组a中的元素在二叉树中按照由上至下，由左至右的顺序排序
  

  初始化.jpg

• 调整堆元素

  
  调整堆.jpg

• 堆排序
  堆的排序过程实际上是对堆进行调整的过程，由于每次调整完成的堆的根元素为当前堆中的最大元素，对堆进行n（待排序元素的个数）次调整后即完成了排序过程

设计目标元素查找算法

1. 分别定义指针i、j、k；初始化i = 0、j = 1、k = n - 1（n 为数组Arr的长度，该数组元素非递增排序）

   
   指针初始化.png
2. 如果Arr[i] + Arr[j] > target，则j++
   大于target.png
3. 如果j == k; Arr[i] + Arr[j] > target，则i--；j = i - 1
   大于target-1.png
   大于target-2.png
4. 如果j == k; Arr[i] + Arr[j] > target，则not found
   not found.png
5. 如果Arr[i] + Arr[j] < target，则i--; k = j - 1; j = i - 1
   小于target.png

小于target-1.png

6. 如果i < k，则not found
   not found-1.png
7. 否则，返回满足条件的两个元素

在有序数组A，B中查找目标元素

• 如果target是偶数，则分别在A，B中通过目标元素查找算法查找目标元素
• 如果target是奇数，则综合A，B通过目标元素查找算法查找目标元素

算法实现

/**
 返回满足条件的两个目标元素

 @param arrA 数组A
 @param arrB 数组B
 @param sizeA 数组A的长度
 @param sizeB 数组B的长度
 @param target 目标值
 @return 满足条件的两个目标元素数组
 */
int* twoElements(int *arrA, int *arrB, int sizeA, int sizeB, int target) {
    int k = sizeB;
    int *resultElements = (int *)malloc(sizeof(int) * 2);
    for (int i = 0; i < sizeA; i++) {
        int a = *(arrA + i);
        for (int j = 0; j < k; j++) {
            int b = *(arrB + j);
            if (a + b == target) {
                resultElements[0] = a;
                resultElements[1] = b;
                return resultElements;
            } else if (a + b < target) {
                k = j;
                break;
            }
        }
    }
    return nil;
}

/**
 调整数组数据

 @param nums 数组
 @param i 根节点序号
 @param size 数组的长度
 */
void sift(int *nums, int i, int size) {
    while (2 * i < size) {
        int j = 2 * i + 1;
        // 左孩子节点
        int left = *(nums + j);
        int temp = left;
        // 判断是否存在右孩子
        if (j + 1 < size) {
            // 存在右孩子
            int right = *(nums + j + 1);
            // temp暂存左右孩子中的较大者
            if (right > temp) {
                temp = right;
                j++;
            }
        }
        // 如果根节点值不大于左孩子|右孩子
        if (temp > *(nums + i)) {
            *(nums + j) = *(nums + i);
            *(nums + i) = temp;
        }
        i = j;
    };
}

/**
 堆排序

 @param nums 数组
 @param size 数组长度
 */
int* heapSort(int *nums, int size) {
    // 建大根堆
    for (int i = size/2 - 1; i >= 0 ; i--) {
        sift(nums, i, size);
    }
    // 排序
    int *result = (int *)malloc(sizeof(int) * size);
    int j = 0;
    for (int i = 0; i < size; i++) {
        *(result + j) = *nums;
        j++;
        *nums = *(nums + size - i - 1);
        sift(nums, 0, size - i - 1);
    }
    return result;
}

/**
 查找数组中和为目标值的两个数

 @param nums 给定数组
 @param numsSize 数组长度
 @param target 目标值
 @return 数组中和为目标值的两个数
 */
int *twoSum(int *nums, int numsSize, int target) {
    int *resultElements = (int *)malloc(sizeof(int) * 2);
    // 定义数组numsA, 存放奇数元素
    int *numsA = (int *)malloc(sizeof(int) * numsSize);
    // 定义数组numsB, 存放偶数元素
    int *numsB = (int *)malloc(sizeof(int) * numsSize);
    // 添加元素到numsA、numsB
    int j = 0;
    int k = 0;
    for (int i = 0; i < numsSize; i++) {
        if (*(nums + i) % 2) {
            // 奇数
            numsA[j] = *(nums + i);
            j++;
        } else {
            // 偶数
            numsB[k] = *(nums + i);
            k++;
        }
    }
    // 分别对数组numsA、numsB的元素进行堆排序
    int *sortA = heapSort(numsA, j);
    int *sortB = heapSort(numsB, k);
    if (target % 2) {
        // 奇数, 则满足条件的元素一个在sortA中, 一个在sortB中
        resultElements = twoElements(sortA, sortB, j, k, target);
    } else {
        // 偶数, 则满足条件的元都在sortA中或sortB中
        resultElements = twoElements(sortA, sortA + 1, j, j - 1, target);
        if (!resultElements) {
            resultElements = twoElements(sortB, sortB + 1, k, k - 1, target);
        }
    }
    
    free(numsA);
    free(numsB);
    free(sortA);
    free(sortB);
    return resultElements;
}