[算法学习]给定一个整型数组，找出两个整数为指定整数的和(1)

算法

问题描述：给定一个整型数组，是否能找出其中的两个数使其和为某个指定的值？（假定是无序数组）

解法一：暴力破解（穷举法，不提倡）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * 暴力破解
 * (穷举，时间复杂度：O(n^2)，正常是不会用这个滴，假如只是为了快速解题，对时间没有限制，用这个最简单)
 *
 * @param nums
 * @param target
 */
public static void findTwo1(int[] nums, int target)
{
    int one, two;
    for (int i = 0; i < nums.length; i++)
    {
        one = nums[i];
        two = target - one;
        for (int j = 0; j < nums.length; j++)
        {
            if (i != j)
            {
                if (two == nums[j])
                {
                    System.out.println("one:" + one + " two:" + two);
                    return;
                }
            }
        }
    }
    System.out.println("找不到这两个数");
}

解法二：二分法（相当于用两个指针）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * 两个指针二分查找
 * (排序时间复杂度为O(nlog(n)),while最多O(N)，所以最终程序的时间复杂度为：O(nlo(n)))
 *
 * @param nums
 * @param target
 */
public static void findTwo2(int[] nums, int target)
{
    // 1.排列（用的是Dual-Pivot Quicksort(快速排序),时间复杂度为O(nlog(n))）
    Arrays.sort(nums);
    // 2.类二分查找
    int left = 0;
    int right = nums.length - 1;
    while (left < right)
    {
        if (nums[left] + nums[right] > target)
        {// 太大 right减少
            right--;
        }
        else if (nums[left] + nums[right] < target)
        {// 太小left增加
            left++;
        }
        else
        {// 找到结果，结束查找
            System.out.println("one:" + nums[left] + " two:" + nums[right]);
            return;
        }
    }
    System.out.println("找不到这两个数");
}