确定是否数组包含两个元素这等于一定数额？ [英] Determine if array contains two elements which equal a certain sum?

问题描述

数组

  //检查是否包含两个元素的总和为s。
//输入：数字列表和一个整数s
//输出：返回true，如果答案是肯定的，否则返回FALSE

公共静态布尔calvalue（INT []号，int类型）{
的for（int i = 0; I＆LT; numbers.length;我++）{
    对于（INT J = I + 1; J＆LT; numbers.length; J ++）{
        如果（数字[1]  - ;多个）{
            如果（编号[I] +号[J] == S）{
                返回true;
                }
            }
        }
    }
    返回false;
}
 

解决方案

这可以在O（n）的实现。

1. 创建一个散列集支持你的列表中，这样它包含列表中的所有元素。这需要为O（n）。
2. 在走过的每个元素 N 您的清单，计算 SN = D 中，并检查presence的 D 在集合。如果 D 是present，那么 N + D = S ，所以返回真。如果您在列表中通过没有找到一个合适的 D ，返回假。这是一个通过你的列表来实现，每个查找取O（1），所以这一步还需要O（N）。

// Checks whether the array contains two elements whose sum is s.
// Input: A list of numbers and an integer s
// Output: return True if the answer is yes, else return False

public static boolean calvalue (int[] numbers, int s){
for (int i=0; i< numbers.length; i++){
    for (int j=i+1; j<numbers.length;j++){
        if (numbers[i] < s){
            if (numbers[i]+numbers[j] == s){
                return true;
                }
            }
        }
    }
    return false;
}

解决方案

This can be achieved in O(n).

1. Create a hash-backed set out of your list, such that it contains all elements of the list. This takes O(n).
2. Walk through each element n of your list, calculate s-n = d, and check for the presence of d in the set. If d is present, then n+d = s, so return true. If you pass through the list without finding an appropriate d, return false. This is achieved in a single pass through your list, with each lookup taking O(1), so this step also takes O(n).

这篇关于确定是否数组包含两个元素这等于一定数额？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！