- return false the time complexity is ( )where is the length of the array the space complexity is ( )since the subarray can be represented by two variables identifying the right invariant is an art the key strategy to determine whether to use an invariant when designing an algorithm is to work on small examples to hypothesize the invariant oftenthe invariant is subset of the set of input spacee ga subarray table top tips for invariants the -sum problem design an algorithm that takes as input an array and numberand determines if there are three entries in the array (not necessarily distinctwhich add up to the specified number for exampleif the array is then there are three entries in the array which add up to ( and (note that we can use twicesince the problem statement said we can use the same entry more than once howeverno three entries add up to hinthow would you check if given array entry can be added to two more entries to get the specified numbersolutionfirstwe consider the problem of computing pair of entries which sum to assume is sorted we start with the pair consisting of the first element and the last element( [ ] [ ]let [ [ if kwe are done if kwe increase the sum by moving to pair ( [ ] [ ]we need never consider [ ]since the array is sortedfor all ia[ [ < [ [ kwe can decrease the sum by considering the pair ( [ ] [ ])by analogous reasoningwe need never consider [ again we iteratively continue this process till we have found pair that sums up to or the indices meetin which case the search ends this solution works in (ntime and ( space in addition to the space needed to store now we describe solution to the problem of finding three entries which sum to we sort and for each [ ]search for indices and such that aja[kt [ithe additional space needed is ( )and the time complexity is the sum of the time taken to sorto( log )and then to run the (nalgorithm described in the previous paragraph times (one for each entry)which is ( overall the code for this approach is shown below def has_three_sum (at) sort (finds if the sum of two numbers in equals to return anyhas_two_sum (at afor in athe additional space needed is ( )and the time complexity is the sum of the time taken to sorto( log )and then to run the (nalgorithm to find pair in sorted array that sums to specified valuewhich is ( overall variantsolve the same problem when the three elements must be distinct for exampleif and then [ [ [ is not acceptablea[ [ [ is not acceptablebut [ [ [ and [ [ [ are acceptable